3 ms·
Some permutations have one cycle, other have more. You are "adjusting" your permutation from 4 3 0 5 1 2 to 3 0 5 1 2 4 to eliminate a cycle and obtain a suitab
by HelloNurse 9y ago
Some permutations have one cycle, other have more. You are "adjusting" your permutation from 4 3 0 5 1 2 to 3 0 5 1 2 4 to eliminate a cycle and obtain a suitable result.
What are the rules to do that and ensure the single-cycle permutations are produced with uniform probability if the original permutation is produced with uniform probability?
I.e. which set of n permutations is mapped to each single cycle permutation?
It's going to be a much more complex algorithm than the optimal in-place shuffles discussed in the article.
- justinpombrio 9y agoNo... it's pretty clear that there are exactly n ways to get each particular single-cycle permutation, given by the n rotations of the fisher-yates shuffle. For example, if you rotate the parent's shuffle by one: 2, 4, 3, 0, 5, 1 you get the same single-cycle permutation. I think this might actually lead to a easier proof than in the article.