Randomize a List problem

[Albert Chan]

To swap 2 items from the stack, we can do with 2 PICK / 2 UNPICK

≪ → n m ≪ n PICK m 1. + PICK n 1. + UNPICK m UNPICK ≫≫

named this 'nmswap'. Code work even if n = m

50 40 30 20 10
3 3 nmswap       → 50 40 30 20 10
3 4 nmswap       → 50 30 40 20 10

[John Keith]

A few more random observations about the original (incorrect) RANL program:

The first iteration does nothing because the argument for ROLLD can never be greater than 1. The program would run faster starting 2 t FOR n...

The first element in the list can't move until the last iteration and has only 1 chance in n of ever doing so.

The indices of the permutations (see post #12) that the program can return are curious indeed:

Code:


{ 1 2 3 }
  1, 2, 3, 5

{ 1 2 3 4 }
  1, 2, 3, 4, 5, 6, 13, 14, 19, 20

{ 1 2 3 4 5 }
  1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 49, 50, 51, 53, 73, 74, 77, 97, 98, 101

For a list of 6 elements, the first 24 permutations are returned, and the last 101 are not. The rest of the list is similarly chaotic.

Note that I have used lists of 1..n rather than n..1 as in HLIB's first post.

[Albert Chan]

(09-17-2020 12:20 PM)John Keith Wrote:  A few more random observations about the original (incorrect) RANL program:

The first iteration does nothing because the argument for ROLLD can never be greater than 1.
The program would run faster starting 2 t FOR n...

Your optimization works, as long as the list has more than 1 item.
With a starting of 2, this meant it is possible to hit with 2 ROLLD, even if t=1

For most other programming languages, this is not a problem.
However, HP-50g has a FOR loop quirk, that *always* run the loop at least once.

≪ 2. 1. FOR n n NEXT ≫ EVAL       → 2.

To see the actual problem, lets save RANL "optimization" under 'RANL2'

≪ LIST➝ ➝ t
≪ 2. t FOR n n RAND × CEIL ROLLD NEXT t ➝LIST ≫ ≫

Starting with an empty stack:

{10.}
RANL2       → "ROLLD Error: Too few Arguments", now stack = 10, 2
{20.}
RANL2       → 10., 2., {20.} ok
RANL2       → 10. 20., {2.} ???

[John Keith]

(09-17-2020 01:42 PM)Albert Chan Wrote:  Your optimization works, as long as the list has more than 1 item.
With a starting of 2, this meant it is possible to hit with 2 ROLLD, even if t=1

...

True enough,but...

a) Nobody would want to use the program anyway, other than to study its unusual properties.

b) There are other RPL commands such as PiLIST and SigmaLIST that choke on lists with one element.

I was merely pointing out that the first iteration has no effect. I probably should not have written

The program would run faster starting 2 t FOR n...

[John Keith]

I did some tests on the frequencies of the permutations returned by the original program and as expected they are far from uniform.

For { 1 2 3 } the percentages range from about 15% to about 33%. the expected value would be 25%. (1 out of the 4 permutations returned)

For { 1 2 3 4 } the percentages range from about 4% to about 16%. The expected value would be 10%. (1 out of the 10 permutations returned)

In most test runs that I did the 2nd permutation was most common, and the last permutation returned by the program was the least common.

[Albert Chan]

(09-18-2020 03:31 PM)John Keith Wrote:  In most test runs that I did the 2nd permutation was most common, and
the last permutation returned by the program was the least common.

Least common permutations are permutations that RANL *never* produced.
For n-items list, RANL does n! ways, ideal probability of each permutations is 1/n!

Example {1,2,3,4}, out of 4! = 24 ways, RANL produced:
(Out of 24, frequencies of all 1's is ideal, P = 1/24 ≈ 4.17%)

Code:

Pat  Freq
1234    4
1243    4
1324    3
1342    2
1423    3
1432    2
3124    2
3142    1
4123    2
4132    1

RANL generated g = 10 permutations. Missing permutations = 4! - 10 = 14, all having P = 0%
Trivia: 1 cannot be shuffled beyond its neighbors. Those accounted for 12 missing permutations.

Here are RANL missing permutations percentages, for n-items list (smaller is better)

Code:

n    g   missing permutations = 1 - g/n!
3    4   33.33%
4   10   58.33%
5   28   76.67%
6   80   88.89%
7  274   94.56%
8  898   97.77%

[Albert Chan]

(09-18-2020 10:19 PM)Albert Chan Wrote:  Here are RANL missing permutations percentages, for n-items list (smaller is better)

Code:

n    g   missing permutations = 1 - g/n!
3    4   33.33%
4   10   58.33%
5   28   76.67%
6   80   88.89%
7  274   94.56%
8  898   97.77%

To generate above chart, we can build from previous cases.

For example, to extend n=4 to n=5, we add 1 to all, then prepend a 1:

12345 ×4
12354 ×4
12435 ×3
...

For each pattern, slide last entry to the left, generate n patterns each, like this:

(12345, 12354, 12534, 15234, 51234) ×4
(12354, 12345, 12435, 14245, 41245) ×4
(12435, 12453, 12543, 15243, 51243) ×3
...

Collect like patterns, we got the n=5 permutations distributions.

Trivia: top entry can only be 1, and set of slided bottom entries
Trivia: bottom entry can only be itself, or its neighbor.

[pier4r]

Info. If I am not wrong, in this thread https://www.hpmuseum.org/forum/thread-8555.html and this thread http://www.hpmuseum.org/forum/thread-8209.html we already analyzed with DavidM that one of the originally mentioned "randomize list" was not random enough, or incorrect.

This because I was making a solver of a little game, where numbers and operators needed to be combined to get a certain number. The search was random and sometimes it took extremely long. Checking the frequencies, there were some permutations that were very rare or some elements weren't shuffled at all. At the moment I do not remember exactly were the discussion was.

[DavidM]

(10-13-2020 07:13 PM)pier4r Wrote:  ...This because I was making a solver of a little game, where numbers and operators needed to be combined to get a certain number. The search was random and sometimes it took extremely long. Checking the frequencies, there were some permutations that were very rare or some elements weren't shuffled at all. At the moment I do not remember exactly were the discussion was.

I recall that you discovered a problem in an earlier version of the LSHUF command that resulted from its use of the SplitMix64 algorithm for shuffling. I'm pretty sure the issue resulted from the trailing low-order bits of the SplitMix64 result having a cycle of some sort. Since most implementations convert the result into a real number by dividing it by 2^64, the influence of those bits is very low in common use. In the case of LSHUF, the SplitMix64 result is instead treated as an integer for a MOD operation. Those last bits were creating a very noticeable bias and the fix was simply to discard the last 4 bits by shifting the 60 high-order bits to the right.

There's probably something in that very long thread about it. Or perhaps in an email discussion? I no longer remember where the discussion took place. Nor did a quick search find any mention of SplitMix64 having this issue, so my memory could be totally wrong. But I did make a specific change to the LSHUF code to shift out the last 4 bits of the SplitMix64 output, and I wouldn't have done that arbitrarily. Wish I had put the specific reason in the comments.

[pier4r]

The worst case is that the discussion was private. Then either it is up to us to find it or it is lost (unfortunately).

If it is in the long threads, one day will pop out because someone will find it.

edit: I see that some part of the discussion are in PMs between me and you in this forum. Let me know what we can do about it.
But then it is clear that is not exactly related to the RANL program.

[Albert Chan]

(10-14-2020 04:12 AM)DavidM Wrote:  In the case of LSHUF, the SplitMix64 result is instead treated as an integer for a MOD operation. Those last bits were creating a very noticeable bias and the fix was simply to discard the last 4 bits by shifting the 60 high-order bits to the right.

It is a bad idea to use modulo to pick random elements.
see http://www.azillionmonkeys.com/qed/random.html

This is especially bad for shuffling list. Bias accumulate.

First pick has a slight bias toward element x
Second pick has a slight bias toward element y ...
By the time shuffling is complete, bias is noticeable, heavily toward {x, y, ...}

Good shuffling required unbiased ranged randoms, *and* good random number generator.
see https://www.pcg-random.org/posts/bounded-rands.html

(10-09-2020 04:52 PM)pier4r Wrote:  Then I thought: what are the odds that we sit, without noticing each other, near to each other?

This reminds me of pier4r's Little math problem(s) October 2020
Chance of encounter (each day) is miniscule. But, months goes by, what were rare is not rare anymore.

[DavidM]

(10-15-2020 04:43 PM)Albert Chan Wrote:  It is a bad idea to use modulo to pick random elements.
see http://www.azillionmonkeys.com/qed/random.html

This is especially bad for shuffling list. Bias accumulate.

The method described in that same link to mitigate the problem using a range check is exactly what LSHUF does. Any intermediate results for the random integer that are outside the range identified are rejected, and the next value is computed until it is in range.

[David Hayden]

Coming back to this after rediscovering One Minute Marvels.

The original algorithm is basically this:

Code:

T = size of list
For n = 1 to t
    R = random number from 1 to n
    Rotate the last R items of the list to the right

Consider the first item in the list. The only time it can move is on the last loop iteration when n=t, and even then, only when R=t, which has probability 1/t Also, since the algo rotates the list, the first item can only move to position 2.

Similarly, the second item can only move during the last or second-to-last iteration. It can move to position 3 or 4.

And so on down the line. Here’s a table showing where the items can move to for a 9-item list. Each row represents the starting position of an item and each colunm is a possible ending positions:

Code:

     1 2 3 4 5 6 7 8 9
1    * *
2      * * *
3        * * * *
4          * * * * *
5    *       * * * * *
6    * * *     * * * *
7    * * * * *   * * *
8    * * * * * * * * *
9    * * * * * * * * *

Only items 8 and 9 can land in all positions.

[DavidM]

(04-25-2024 04:50 PM)David Hayden Wrote:  Coming back to this after rediscovering One Minute Marvels.

Very nice sleuthing, David! I'd guess you spent more than "1 minute" to trace the outcomes. Nice work.