Randomize a List problem

[Hlib]

Over the weekend, I did a little research using a calculator. This is a program called "Randomize a List", taken from the wonderful manual <One-Minute Marvels> (a collection of short HP48/49 programs, page 8) by Wlodek Mier-Jedrzejowicz and Richard Nelson.
`RANL`

Code:


<< LIST➝ ➝ t
<< 1. t FOR n n RAND × CEIL ROLLD NEXT t ➝LIST >> >>

`RANL` shuffles the list items randomly. Theoretically, the number of different lists of N elements is N!. This program cannot output any of all possible options when it is run once.
For example, we will never get permutations {1 2 3} and {2 1 3 }
after {3 2 1} `RANL`
The number of all possible options we can get for a list of N elements in this program when it is run once:
#2 {2 1} – 2 options out of 2!=2 possible.
#3 {3 2 1} – 4 options out of 3!=6 possible.
#4 {4 3 2 1} – 10 out of 4!=24.
#5 {5 4 3 2 1} – 28 / out of 5!=120.
#6 {6 5 4 3 2 1} – 80 / out of 6!=720.
#7 {7 6 5 4 3 2 1} – 274 / out of 7!=5040.
#8 {8 7 6 5 4 3 2 1} – 898 / out of 8!=40320 and so on.
To fix this, you need to replace one letter in the text: ... FOR n t RAND × ... .
But I`m interested in a more complex problem: how to use the formula to express the number of possible combinations in the first (not corrected) version of the program, also describing the ROLLD function in the loop. I calculated this using an algorithm on a calculator, and my knowledge of mathematics is clearly not enough for an analytical solution.

[John Keith]

Here is a good Wikipedia article describing the algorithm behind the RANL program. If you read farther down, it says that a simple programming mistake can accidentally implement Sattolo's algorithm which returns only cyclic permutations.

If that was exactly what was going on, you should be getting (n-1)! permutations, which you are not. I am not sure that the corrected version of the program does produce all permutations, nor whether the incorrect version is in fact the mistake noted in the linked article. I suspect the problem is more complex.

By the way, I searched http://oeis.org/ with the numbers you listed but no result was returned. Are you sure you have found all the possible permutations that the incorrect version can produce?

[Albert Chan]

Random shuffling must produce all permutations with equal probabilities.

We pick a random element from the list, and moved out of the way
Do this repeatedly, like this. (we can skip the 1 element list case)

Code:

function shuffle(lst)
    local n = #lst
    for i = n, 2, -1 do
        local j = random(i)
        lst[i], lst[j] = lst[j], lst[i]
    end
end

1st loop, random element is swapped to lst[n], and never touched again.
2nd loop, random element is swapped to lst[n-1] ...

lua> pat = setmetatable({}, {__index = function(a,i) return 0 end})
lua> for i=1,120000 do
:            lst = {'1','2','3'}
:            shuffle(lst)
:            x = table.concat(lst,'')
:            pat[x] = pat[x] + 1
:      end
lua> table.foreach(pat, print)
321       20104
312       19844
132       20026
123       20096
231       19890
213       20040

[Hlib]

Quote: John Keith wrote:
... I am not sure that the corrected version of the program does produce all permutations, nor whether the incorrect version is in fact the mistake noted in the linked article. ... Are you sure you have found all the possible permutations that the incorrect version can produce?

For simple cases you can check this manually:
#3: 321 312 231 132
#4: 4321 4312 4231 4213 4132 4123 2431 2413 1432 1423
No matter how many times we run program
<< { 3. 2. 1 } LIST➝ ➝ t
<< 1. t FOR n n RAND × CEIL ROLLD NEXT t ➝LIST >> >>
or
<< { 4. 3. 2. 1 } LIST➝ ➝ t
<< 1. t FOR n n RAND × CEIL ROLLD NEXT t ➝LIST >> >>
we won`t get any other results.
But if ... FOR n t RAND ... then after many clicks we may get all set of lists (6 for #3 and 24 for #4).
Assuming that RAND can take any value from the interval [0,1] and taking into account the specifics of the ROLLD command, I calculated all possible options for the shown results for both versions of the program using the full search method.
There is no error here. But let`s say we can`t be sure. So we need to get the formula.

Quote: Albert Chan wrote:
Random shuffling must produce all permutations with equal probabilities.
We pick a random element from the list, and moved out of the way
Do this repeatedly, like this. (we can skip the 1 element list case) ...

Thank you, but that`s not exactly what I meant. It is easy to randomize the list in different ways, for example, in CASIO-BASIC:

Code:

(Shuffling the List 2)
Seq(Ran# ,K,1,Dim List 2,1)➝List 1
SortA(List 1,List 2):Disp List 2

I was interested in the possibility of describing by formula of the algorithm that was given in the RPL-program.

[Albert Chan]

Confession time. I have never program in HP-50g.
This is my first program, after skimming the online manual

To move random element out of the way, I do it in 2 steps.
ROLL it to top-of-stack, then ROLLD it to bottom-of-stack.

≪ { 3. 2. 1 } LIST➝ ➝ t
≪ t 2. FOR n n RAND × CEIL ROLL t ROLLD -1 STEP t ➝LIST ≫ ≫

We can also replace "t ROLLD" to "n ROLLD", possibly run faster ?

P.S.
possibly non-issue. "n RAND × CEIL" might return an index of 0
But, on the emulator 0 ROLL ≡ 1 ROLL ≡ do nothing.

[Albert Chan]

(09-14-2020 08:51 PM)Hlib Wrote:  FOR n t RAND ... then after many clicks we may get all set of lists (6 for #3 and 24 for #4).
Assuming that RAND can take any value from the interval [0,1] and taking into account the specifics of the ROLLD command, I calculated all possible options for the shown results for both versions of the program using the full search method. There is no error here. But let`s say we can`t be sure. So we need to get the formula.

For a list of 3 items, we have 3! = 6 permutations.
But, your suggested shuffling can have 3*3*3 = 27 ways.

By the pigeonhole principles, some will appear more often, some less (*)
Starting from {3,2,1}, and gone thru all 27 possible ROLLD shuffling, we have:

{3,2,1} × 5
{2,3,1} × 4
{3,1,2} × 5
{1,3,2} × 5
{2,1,3} × 4
{1,2,3} × 4

Shuffling will not be fair. I did a simulation, and confirmed this.

(*) even if one divides the other, there is still a possibility of unfair shuffling, depending on shuffling details.

[Wes Loewer]

(09-15-2020 01:00 AM)Albert Chan Wrote:  For a list of 3 items, we have 3! = 6 permutations.
But, your suggested shuffling can have 3*3*3 = 27 ways.

I was just about to point out the same thing, implying that the probabilities are not all equal. Just for fun, here's my attempt at randomizing a list with equal probabilities.

<< { } 1. PICK3 SIZE START RAND + NEXT SWAP 2. ->LIST TRAN SORT TRAN 2. GET >>

[Werner]

(09-14-2020 11:41 PM)Albert Chan Wrote:  possibly non-issue. "n RAND × CEIL" might return an index of 0
But, on the emulator 0 ROLL ≡ 1 ROLL ≡ do nothing.

Long ago, it has been confirmed by Those Who Know that RAND will never return 0. or 1., so 1. <= n RAND * CEIL <= n

Cheers, Werner

[Werner]

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

or, the other way round:
≪ 1. t FOR n t ROLL n RAND × CEIL ROLLD NEXT t ➝LIST ≫

Cheers, Werner

[John Keith]

(09-14-2020 08:51 PM)Hlib Wrote:  For simple cases you can check this manually:
#3: 321 312 231 132
#4: 4321 4312 4231 4213 4132 4123 2431 2413 1432 1423
No matter how many times we run program
...
I was interested in the possibility of describing by formula of the algorithm that was given in the RPL-program.

Well, I checked and not all of the permutations you listed are cyclic permutations so we can scratch that idea. Also we can note that the number of permutations returned by the erroneous program grows much more slowly than (n-1)! As to the formula that explains the program behavior, I have no idea.

[Hlib]

Thanks everyone!
In our examples, can we estimate the number of different combinations for lists of any size? There may be unexpected results.
I inserted a fragment into the source program, which swaps 1-st and random n-th elements on stack:

Code:

<< { } LIST➝ ➝ t
<< 1. t FOR n t RAND × CEIL
PICK LASTARG SWAP UNROT UNPICK
NEXT t ➝LIST >> >>

Results are:
#2 {2 1} – 2 options out of 2!=2 possible.
#3 {3 2 1} – 6 options out of 3!=6 possible.
#4 {4 3 2 1} – 24 / out of 4!=24.
#5 {5 4 3 2 1} – 107=5!–13 / out of 5!=120.
#6 {6 5 4 3 2 1} – 685=6!–35 / out of 6!=720.
For many practical problems we don`t need to have equal probabilities for each permutation, and we don`t always need the maximum number of possible combinations. But in these short programs before using them I would like to estimate at least the range of results that we get using the stack process.

[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))

[ijabbott]

(09-15-2020 09:47 AM)Werner Wrote:  

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

or, the other way round:
≪ 1. t FOR n t ROLL n RAND × CEIL ROLLD NEXT t ➝LIST ≫

Cheers, Werner

Those two are the classic Fisher-Yates shuffle algorithm, with the ROLL and ROLLD exchanging two items at specified stack positions. Is there a more efficient way to swap stack elements?

[Albert Chan]

(09-15-2020 03:57 PM)Hlib Wrote:  I inserted a fragment into the source program, which swaps 1-st and random n-th elements on stack ...

Do not use this code ! This is much worse than "random(t) ROLLD"

Code:

Starting pattern = 123, shuffled pattern has 3^3 = 27 ways

Pattern swap 1st random(t) ROLLD
123     7        5
132     2        4        
213     6        5
231     3        5
312     3        4
321     6        4

Uneven probabilities problem get worse with more items in the list.
This is not just pigeonhole issues anymore.

I would recommend not cutting corners here, and use good shuffling code.

Code:

Starting pattern = 1234, shuffled pattern has 4^4 = 256 ways

Pattern swap 1st random(t) ROLLD
1234    34       15
1243    8        7
1324    8        14
1342    3        14
1423    3        7
1432    8        7
2134    24       15
2143    4        7
2314    14       15
2341    4        15
2413    4        7
2431    14       7
3124    14       14
3142    4        14
3214    24       14
3241    14       14
3412    4        14
3421    4        14
4123    4        7
4132    14       7
4213    14       7
4231    24       7
4312    4        7
4321    4        7

[John Keith]

(09-15-2020 06:39 PM)ijabbott Wrote:  Those two are the classic Fisher-Yates shuffle algorithm, with the ROLL and ROLLD exchanging two items at specified stack positions. Is there a more efficient way to swap stack elements?

In UserRPL I can't think of a faster way. Stack operations are generally faster than list operations.

There are two ListExt commands that are germane to the current discussion:

LSHUF implements the modern Fisher-Yates algorithm and is many times faster than any user implementation.

DOPERM lists all permutations of a list taken n items at a time (see documentation).

For instance, Albert's example of the 100th permutation of { 1 2 3 4 5 } would be

{ 1 2 3 4 5 } 5 << >> DOPERM 100 GET

[Albert Chan]

(09-15-2020 08:56 PM)John Keith Wrote:  In UserRPL I can't think of a faster way. Stack operations are generally faster than list operations.

Hi, John Keith

Can you show what a list-operated shuffling code look like ?
With both input and output a list, I would have guessed list-operated shuffle faster.

[Werner]

(09-15-2020 09:34 PM)Albert Chan Wrote:  Can you show what a list-operated shuffling code look like ?
With both input and output a list, I would have guessed list-operated shuffle faster.

To swap two positions in a list:
In: L i j
Out: L, positions i and j swapped

Code:

\<<
    ROT SWAP DUP2 OVER
    6 PICK GET PUT
    4 ROLLD GET PUT
\>>

Stack operations are orders of magnitude faster, because the stack contains only pointers. The above code rebuilds the whole list twice (with each PUT). And yes, for the 49 and up it can be made 1 instruction shorter still (replace ROT SWAP with UNROT - purists will notice that that is not the same, but it is here).
There is no way (short of machine language) to swap two objects in a list in-place.

BTW the original 'randomize list' can be written in a much more compact way:

Code:

\<<
 1.
 \<< NSUB RAND * CEIL ROLLD \>>
 DOSUBS
\>>

Cheers, Werner

[John Keith]

(09-16-2020 06:43 AM)Werner Wrote:  BTW the original 'randomize list' can be written in a much more compact way:

Code:

\<<
 1.
 \<< NSUB RAND * CEIL ROLLD \>>
 DOSUBS
\>>

Cheers, Werner

That's really neat! Thanks for posting, you explained the stack vs. list issue better than I could have.

[David Hayden]

[ Edit: fixed some typos that Albert Chan pointed out in a private message. Thanks Albert! ]
You can swap level 1 with level N with

Code:

N PICK SWAP N UNPICK

You can use this to swap levels M and N with

Code:

           N PICK SWAP N UNPICK @ swap level n and level 1
           M PICK SWAP M UNPICK @ swap level m and level 1
           N PICK SWAP N UNPICK @ swap level n and level 1

But that won't work if N = M, so it needs to be

Code:

IF N M < THEN  @ EDIT: < should be ≠
           N PICK SWAP N UNPICK @ swap level n and level 1
           M PICK SWAP M UNPICK @ swap level m and level 1
           N PICK SWAP N UNPICK @ swap level n and level 1
           END

With that, you can efficiently sort a list with [ EDIT: "sort" should be "shuffle" ]

Code:

«
LIST➝ 
 @ Subroutine to swap level n with level m
 « ➝ N M « IF N M ‹ THEN
           N PICK SWAP N UNPICK @ swap level n and level 1
           M PICK SWAP M UNPICK @ swap level m and level 1
           N PICK SWAP N UNPICK @ swap level n and level 1
           END
           » »
 ➝ t nmswap
  « t 2. FOR n
    n RAND * CEIL
    n nmswap EVAL
    -1. STEP
    t ➝LIST
  »
»

[Hlib]

Quote:David Hayden wrote
You can swap level 1 with level N with

Code:

N PICK SWAP N UNPICK

You can use this to swap levels M and N with

Code:

           N PICK SWAP N UNPICK @ swap level n and level 1
           M PICK SWAP M UNPICK @ swap level m and level 1
           N PICK SWAP N UNPICK @ swap level n and level 1

But that won`t work if N = M ...

Yes, this method is also quite good, although not elegant enough. Quite by chance,
I found out about the existence of a very important application called
"Extended List Commands Library". Thanks to John Keith for this link:

Quote:John Keith wrote
... Stack operations are generally faster than list operations.
There are two ListExt commands that are germane to the current discussion: ...

Now, to swap two objects in a stack or list, it is much easier to use the m n SWPXY
and m n LSWAP commands from the library.