09-14-2020, 04:38 PM
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`
`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.
`RANL`
Code:
<< LIST➝ ➝ t
<< 1. t FOR n n RAND × CEIL ROLLD NEXT t ➝LIST >> >>
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.