Randomize a List problem

[Albert Chan]

(09-15-2020 09:47 AM)Werner Wrote:  or, the other way round:
≪ 1. t FOR n t ROLL n RAND × CEIL ROLLD NEXT t ➝LIST ≫

This may be easier to understand (and, probably more efficient):
Note: I use lua definition of random(n) = 1 .. n, all equally likely.

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

With k-1 items shuffled, k-th loop ROLL stack(k) to stack(1), then ROLLD to stack(random(k)).
In the meantime, stack(k+1), stack(k+2), ..., had never been touched.

(09-14-2020 11:41 PM)Albert Chan Wrote:  ≪ t 2. FOR n n RAND × CEIL ROLL t ROLLD -1 STEP t ➝LIST ≫

My version give me an idea ...

Say, we changed "t 2." to "t 1." (equivalent to "t ROLLD" before convert back to list).
Now, imagine you know the next sequence of generated random numbers.

If random(n) = 1, 1, 1 ..., shuffled list = original list (1st permutation)
If random(n) = n, n, n ..., shuffled list = reversed list (t! permutation)

We can reverse the process, and get the k-th lexigraphically ordered pattern.
In other words, we can shuffle with k = random(n!), then reconstruct the permutation.

Example: What is 100-th lexigraphically ordered list, [1, 2, 3, 4, 5] ?

Code:

100 - 1 = 99           -- we do calculations, 0-based
99/2 = 49, remainder 1
49/3 = 16, remainder 1
16/4 = 4,  remainder 0
 4/5 = 0,  remainder 4

→ 100 - 1 = [4,0,1,1] * [4!,3!,2!,1!] = 96 + 0 + 2 + 1 = 99
→ Back to 1-based: [4,0,1,1] .+ 1 = [5,1,2,2]

Reconstruct 100-th permutation of [1,2,3,4,5] on Emu-48:

5 4 3 2 1
5 ROLL 5 ROLLD       → 5 4 3 2 1
1 ROLL 5 ROLLD       → 1 5 4 3 2
2 ROLL 5 ROLLD       → 3 1 5 4 2
2 ROLL 5 ROLLD       → 4 3 1 5 2
5 ROLLD                  → 2 4 3 1 5

100-th permutation = [5,1,3,4,2]. Confirmed with actual counting.

>>> from itertools import permutations
>>> for i,x in enumerate(permutations([1,2,3,4,5]),1):
...          if i==100: print(i, x); break
...
(100, (5, 1, 3, 4, 2))