List Commands Library for 50g - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: List Commands Library for 50g (/thread-8555.html) Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 RE: List Commands Library for 50g - Thomas Klemm - 01-28-2019 11:47 PM (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# RE: List Commands Library for 50g - ttw - 01-29-2019 12:16 AM 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<=XLIST 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? RE: List Commands Library for 50g - John Keith - 02-01-2019 08:14 PM (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. RE: List Commands Library for 50g - pier4r - 02-01-2019 10:42 PM 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:start&do=revisions RE: List Commands Library for 50g - Gilles - 05-13-2019 11:36 AM 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? RE: List Commands Library for 50g - DavidM - 05-13-2019 03:43 PM 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. RE: List Commands Library for 50g - DavidM - 05-17-2019 02:53 PM 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! RE: List Commands Library for 50g - Gilles - 05-17-2019 09:43 PM (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.