List Commands Library for 50g

[Thomas Klemm]

(01-27-2019 10:02 PM)Thomas Okken Wrote:  The probability of RAND returning zero is exactly zero. It can't happen.
See http://www.hpmuseum.org/forum/thread-9556.html

Interestingly enough, this is not the case with neither the HP-11C nor the HP-15C:

(10-21-2018 09:03 PM)Thomas Klemm Wrote:  Just try this to get 0:

8.603685347E-1
STO RAN#
RAN#

[ttw]

A quick method to avoid zero (and one which also gives problems) in a pseudo random number generator is to generate uniformly distributed integers over (0,M-1) or (1,M) for some large (prime or power of two or whatever) integer. Then one computed for result X (0<=X<M) the number (2X+1)/2N as either a fraction or a floating point number.

[John Keith]

(01-27-2019 07:07 PM)pier4r Wrote:  About RAND a * b + IP. I used it too at first but it messes up when integers are negative if I am not mistaken.

Sure the mode that works also with arbitrary integers is neat. If you fix it I put it in the collection too. Could you ping me if you do it?

Program has been fixed. Replacing IP with FLOOR is all it took.

[pier4r]

(01-27-2019 06:52 PM)John Keith Wrote:  Edited to fix bug that would cause negative values to be off by 1.

Code:


\<< 3. \->LIST I\->R EVAL OVER - 1. + \-> s b a
  \<<
    IF -105. FS?
    THEN 1. s
      START RAND a * b + FLOOR
      NEXT
    ELSE 1. s
      START RAND a * b + FLOOR R\->I
      NEXT
    END s \->LIST
  \>>
\>>

I am still not convinced. But thanks for the effort!

I mean say we have a range of: -5 to 5. When you do RAND a * b + you pick a value, actually, between 0 - eps and -4 - eps (where eps<1). Then you add 5 to it, so one gets mostly positive integers or zero.

Am I missing something obvious here?

[John Keith]

(01-29-2019 07:00 PM)pier4r Wrote:  I mean say we have a range of: -5 to 5. When you do RAND a * b + you pick a value, actually, between 0 - eps and -4 - eps (where eps<1). Then you add 5 to it, so one gets mostly positive integers or zero.

Am I missing something obvious here?

I don't know, but I just ran the revised program and got a list containing approximately equal numbers of each of the integers from -5 through 5.

Try it yourself: run the program with the arguments 1000, -5, 5 then execute LSORT LRPCT on the resulting list to see the stats.

[pier4r]

Ok went debugging your program. I missed some points, not easy to read in the code at glance.
Your 'a' is not the start of the range (intuitively: a is the start and b is the end).
Rather a is the size of the range, b is the start of it.

Then it is sound yes.

edit: added! http://www.wiki4hp.com/doku.php?id=rpl:s...=revisions

[Gilles]

Hi,

if I found some time, i will try to create a ListExt Library (or a subset) in NewRPL. But I'm afraid about the DOPERM and DOCOMB commands... DavidM, if you read this, what algorithm did you use?

[DavidM]

I ended up spending a lot of time on those, starting down several different algorithmic paths and abandoning ideas at various stages for one reason or another. DOCOMB can be summarized as follows:

Code:

create a "mask" that represents the first group of list elements
for each unique mask:
   split the source list into two lists based on the current mask:
      "selected" list elements
      "remnant" list elements
   execute the supplied user program with the new lists defined above
   determine next lexicographic iteration of the mask
group all results from the above into a final list

DOPERM is similar, but has an inner loop that steps through each permutation of each combination that is found above.

The mask is implemented as a string, with each "character" actually representing a zero-based index of a list element (0-255) for permutations and 0 or 1 for combinations.

In order for this approach to perform reasonably, the routines dealing with the mask are all coded in Saturn assembly.

There are some RPLish quirks that also had to be dealt with, especially for the user-supplied executable. It has to be "prepped" to convert any references to the special variables (XPRM, XCMB, CRMNT) into locals, since they will default to being globals when the user creates the program.

[DavidM]

Here's a couple illustrative examples of how the masks I described above are used. I'm representing the masks in these examples as a string of numbers separated by spaces for clarity.

Combination Masks

Example: a list of 5 items, we want all combinations of 3

Lexicographic stepping for DOCOMB/DOPERM combinations starts with the highest order form and works its way down to the lowest. So the first mask is created with a series of 1s that matches the count of selected elements, followed by 0s for the remainder:

1 1 1 0 0

The mask is then stepped down lexicographically in each iteration of the loop until the lowest order form is found:

1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
...
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

The mask for each iteration is applied to the source list such that the resulting selection contains only the elements that correspond to the 1s. So if our source list is:

{ A B C D E }

...then the resulting combinations that correspond to the iterative masks are:

Code:

Src List/Mask  Resulting Sublist
-------------  -----------------
A B C D E   
1 1 1 0 0      A B C    
1 1 0 1 0      A B   D  
1 1 0 0 1      A B     E 
1 0 1 1 0      A   C D 
1 0 1 0 1      A   C   E 
1 0 0 1 1      A     D E 
0 1 1 1 0        B C D 
0 1 1 0 1        B C   E 
0 1 0 1 1        B   D E 
0 0 1 1 1          C D E

Permutation Masks

Example: a list of 4 items

The first mask is generated with each index matching its zero-based starting position, and is thus already in the lowest-order form:

0 1 2 3

The mask is then stepped lexicographically upward until the highest order permutation is encountered:

0 1 2 3
0 1 3 2
0 2 1 3
...
3 1 2 0
3 2 0 1
3 2 1 0

The mask is applied to the source list in a similar fashion to the above description for combinations, but instead of a binary disposition (include/exclude), the mask designates the final positions of each of the source elements in the new list. So if our source list is:

{ A B C D }

...then the resulting permutation lists that correspond to the designated masks are as follows:

Code:

Src List/Mask  Resulting Permutation
-------------  ---------------------
A B C D
0 1 2 3        A B C D 
0 1 3 2        A B D C 
0 2 1 3        A C B D 
0 2 3 1        A C D B 
0 3 1 2        A D B C 
0 3 2 1        A D C B 
1 0 2 3        B A C D 
1 0 3 2        B A D C 
1 2 0 3        B C A D 
1 2 3 0        B C D A 
1 3 0 2        B D A C 
1 3 2 0        B D C A 
2 0 1 3        C A B D 
2 0 3 1        C A D B 
2 1 0 3        C B A D 
2 1 3 0        C B D A 
2 3 0 1        C D A B 
2 3 1 0        C D B A 
3 0 1 2        D A B C 
3 0 2 1        D A C B 
3 1 0 2        D B A C 
3 1 2 0        D B C A 
3 2 0 1        D C A B 
3 2 1 0        D C B A

Stepping algorithm

The heart of all of this is a subroutine I called "NextMask", which takes a mask and a boolean indicating up/down stepping and returns the next mask and a boolean indicating if the new mask is at the high/low extreme. The algorithm is a modified form of this one, with the modifications allowing for up or down stepping. No changes were needed to accommodate combinations and permutations; the exact same algorithm inherently works for both so long as they are formatted as described above.

Hope this helps!

[Gilles]

(05-17-2019 02:53 PM)DavidM Wrote:  Here's a couple illustrative examples of how the masks I described above are used. I'm representing the masks in these examples as a string of numbers separated by spaces for clarity.
Hope this helps!

Yes. Thank you very much for those explanations.

[John Keith]

Version 1.3 has been released: ListExt 1.3

This is a major update with many new commands.

[DavidM]

(01-18-2021 06:37 PM)John Keith Wrote:  Version 1.3 has been released: ListExt 1.3

This is a major update with many new commands.

Here's a quick rundown of the new commands. Many of the new commands operate identically to GoferLists commands with similar names, but are included in ListExt due to improved performance.

Short descriptions of the new commands are listed below, along with the general release notes. As always, complete descriptions and more examples are provided in the documentation that comes with the library.

Questions, comments, etc. are always welcome!

- David

Code:

LSCAN - returns a list of results from applying a program with each successive list element given
   { 1 2 3 4 5 } « + » LSCAN => { 1 3 6 10 15 }
   { 2 2 2 2 2 } « * » LSCAN => { 2 4 8 16 32 }
    
LMAP - maps a command or function to each list element (non-recursive)
   { 1 2 3 4 5 } « 3 * » LMAP => { 3 6 9 12 15 }
   { { 1 2 3 } { 1 2 } { 1 } } ::SIZE LMAP => { 3. 2. 1. }

LXEQ - executes a program repeatedly with each list element as its argument
   { 1 2 3 4 5 } « 3 * » LXEQ => 3 6 9 12 15
      (similar to LMAP, but results are left on the stack instead of grouped into a list)
    { "one" "two" "three" "four" } 4 { NXEQ DISP } CLLCD LXEQ 7 FREEZE => <no stack results>
      (each object is displayed on a separate line starting on line 4 of the display)

LDIFF - returns a list of the elements in list1 that aren't in list2
   { 1 2 3 4 5 } { 2 3 4 5 6 } LDIFF => { 1 }
   { 2 3 4 5 6 } { 1 2 3 4 5 } LDIFF => { 6 }

LINTR - returns a list of the elements that are in both list1 and list2
   { 1 2 3 } { 3 4 5 } LINTR => { 3 }
   { 1 2 3 } { 5 4 3 2 1 } LINTR => { 1 2 3 }

LSUBS - returns a list of all possible subgroupings of the elements in the given list
   { 1 2 } LSUBS => { { } { 1 } { 2 } { 1 2 } }
   { 1 2 3 } LSUBS => { { } { 1 } { 2 } { 1 2 } { 3 } { 1 3 } { 2 3 } { 1 2 3 } }

LFILT - returns a list containing the elements for which the supplied program is TRUE
   { 1 2 3 4 5 } « 2 > » LFILT => { 3 4 5 }
   { 1 2 3 4 5 } { 2 OVER > SWAP 4 > OR } LFILT => { 1 5 }

LWHL - executes a program while a given condition is TRUE, grouping the results into a list
   2 ::NEXTPRIME { 30 < } LWHL => { 2 3 5 7 11 13 17 19 23 29 }
   3 { DUP 2 MOD { 3 * 1 + } { 2 / } IFTE } { 1 SAME NOT } LWHL 1 + => { 3 10 5 16 8 4 2 1 }

LDWHL - removes elements from the beginning of a list that match the provided condition
   { 1 2 3 4 5 } « 4 < » LDWHL => { 4 5 }
   { 1 2 3 4 5 } { 6 < } LDWHL => { }

LTWHL - returns a list containing the first elements of a list that match the provided condition
   { 1 2 3 4 5 } « 4 < » LTWHL => { 1 2 3 }
   { 1 2 3 4 5 } { 6 < } LTWHL => { 1 2 3 4 5 }

LCPRD - returns the Cartesian Product of two or more lists
   { { 1 2 3 } { a b } } LCPRD => { { 1 a } { 1 b } { 2 a } { 2 b } { 3 a } { 3 b } }
   { { 1 } { a b } { X Y Z } } LCPRD => { { 1 a X } { 1 a Y } { 1 a Z } { 1 b X } { 1 b Y } { 1 b Z } }

LTAKE - returns a list containing the first or last elements specified by a count
   { 1 2 3 4 5 } 3 LTAKE => { 1 2 3 }
   { 1 2 3 4 5 } -3 LTAKE => { 3 4 5 }

LDROP - returns a list containing all but the first or last elements specified by a count
   { 1 2 3 4 5 } 3 LDROP => { 4 5 }
   { 1 2 3 4 5 } -3 LDROP => { 1 2 }

LCOMP - returns a list indicating matching and non-matching elements in 2 lists
   { 1 2 3 4 5 } { 5 4 3 2 1 } 1 LCOMP => { 0. 0. 1. 0. 0. }
   { 1 2 3 4 5 } { 5 4 3 2 1 } 0 LCOMP => { 1. 1. 0. 1. 1. }

LDLTA - faster ΔLIST that also accepts lists with 0 or 1 element
   { 1 } LDLTA => { 1 }
   { 5 4 3 2 1 } LDLTA => { -1 -1 -1 -1 }

NL→I2 - converts a list of numbers to an integer (faster, more specific input than NL→I)
   { 1 2 3 } NL→I2 => 123
   { 10 .00299 399 .04E-6 } NL→I2 => 1234

Here's the release notes for this version:

Version 1.3.0
January 4, 2021

- Refactored LRMOV to create a subroutine that could be used by other commands
- Added checks to the following commands for triggering garbage collection in low memory situations:
I→NL
NL→I
- Small speed improvement for SLST→
- Small speed improvement for LPICK
- Negative arguments for LDIST and LSDIV are now allowed; negative indicates quantity of sublists instead of size of each sublist
- LSHUF changes
- optimized to reduce initial list traversal
- reduced subroutine calls during shuffling
- SplitMix64 seed now incremented as per standard definition as opposed to using final output of each iteration as the new seed
- DOCOMB and DOPERM now accept lists and tagged commands for the user-supplied program to execute
- New commands added: LSCAN, LMAP, LXEQ, LDIFF, LINTR, LSUBS, LFILT, LWHL, LDWHL, LTWHL, LCPRD, LTAKE, LDROP, LCOMP, LDLTA, NL→I2
- Updated documentation for new and changed commands

[pier4r]

Awesome a new release! I noticed only now (too little spare time)

Today I had a bit of spare time and I wanted to use LREPL but I noti ed a bit late that it replaces the elements only if there is a match (on the content) and not in the position.

What I wanted is something like this:

{ 1 1 1 1 1 1 1 1 1 1 } @original list
{ 7 8 } @ positions (rather than matching)
{ 77 88 } @replacements

result:
{ 1 1 1 1 1 1 77 88 1 1 }


I dind't find any similar command in ListExt, am I missing something? Should I do a routine on my own?

edit. My solution so far

Code:


LREPLPOS2021Help
  "
  url: '',
  tags: [ 'list', 'replace element' ],
  description:
    When one has a list of replacements for original list
  remarks:
    Not much input checks at first, example: giving positions that they don't exists

  Input:
  L3: originalList
  L2: list of position to replace
  L1: elements to insert (length should be identical to the list of positions to replace)
  Output
  L1: the original list with the elements replaced

  Example(s):
  { 9 8 7 6 5 4 3 2 1 } { 7 8 } { 11 22 } -> { 9 8 7 6 5 4 11 22 1 }
  "

LREPLPOS2021
@ LREPL from ListExtworks works with matching the elements to replace, if one wants to replace
@ with positions one need another routine
\<<
  \->
  @input
  lvOriginList
  lvPositionList
  lvReplacementsList
  @variables
  \<<
    1 lvPositionList SIZE
    FOR lvInd
      lvOriginList
      lvPositionList lvInd GET @the postion
      lvReplacementsList lvInd GET @the replacement
      PUT 'lvOriginList' STO @replaced
    NEXT
    lvOriginList @result
  \>>
\>>

[3298]

Code:

\<< SWAP 2. \<< PUT \>> DOLIST \>>

Untested, but should work. Dispenses with all those unnecessary local variables, and lets DOLIST perform the iteration in place of FOR...NEXT. Perhaps null-tagging PUT instead of wrapping it in a program works too (I can never remember which program-consuming commands like that trick and which ones don't); if it does, then that would be an even better variant.

[Joe Horn]

(07-02-2021 09:41 PM)3298 Wrote:  

Code:

\<< SWAP 2. \<< PUT \>> DOLIST \>>

Untested, but should work. Dispenses with all those unnecessary local variables, and lets DOLIST perform the iteration in place of FOR...NEXT. Perhaps null-tagging PUT instead of wrapping it in a program works too (I can never remember which program-consuming commands like that trick and which ones don't); if it does, then that would be an even better variant.

It works if the SWAP is omitted. Null-tagged ::PUT does not work.

[3298]

(07-03-2021 12:53 AM)Joe Horn Wrote:  It works if the SWAP is omitted. Null-tagged ::PUT does not work.

Oops, apparently I confused the parameter order of PUT with that of UNPICK and ROLLD, where the position parameter is on level 1. Why do they have to be inconsistent like that ... Omitting SWAP is obviously the correct fix here.
And bummer about the null-tag. I assume lists won't be accepted as programs either then. Oh well, how about working around this limitation with DTAG?

Code:

\<< 2. ::PUT DTAG DOLIST \>>

This time I took the time to test: works for me, and it's slightly shorter than the subprogram variant.

[DavidM]

(07-03-2021 07:55 AM)3298 Wrote:  

Code:

\<< 2. ::PUT DTAG DOLIST \>>

That "::<cmd> DTAG" approach is an efficient way to put a non-executed command on the stack for situations like this. Well done!

[pier4r]

nice 3298 ! Didn't think of DSUBS (also because I got burned in the past due to debugging difficulties)

added to https://www.hpmuseum.org/forum/thread-10271.html

[John Keith]

Thanks from me also, 3298.

Here is my variation which allows a single object on level 1 to replace all elements indexed by the list on level2. If level one contains a list, it works just like your program.

Code:


\<< DUP TYPE 5. \=/ { OVER SIZE LMRPT } IFT 2. :: PUT DTAG DOLIST
\>>

For example, if level 1 in Pier4's example is changed to the integer 78, the result will be { 1 1 1 1 1 1 78 78 1 1 }.

[pier4r]

Today while refreshing my PHP (using it on and off, surely less than userRPL), I noticed that there is no similar function like KSORT for PHP arrays (that are like maps). That is, I found no built-in way to say "given an array of integers, order the values, but then please order the other array (containing the indexes) accordingly".

This is how ListExt spoiled me.

For reference: https://www.php.net/manual/en/array.sorting.php