Randomize a List problem

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