@dodicat

Um, not sure what you are trying to prove.

Sattolo introduced his variation in 1986, 48 years after Fisher-Yates hit the streets.

Many websites explain Sattolo's algorithm, and some compare it with the Knuth shuffle. However, none of them give any reason to employ Sattolo rather than Knuth.

With Knuth if we have n elements then we have a potential of n! permutations. With n = 8 we have then 8! (=40,320). With Sattolo if we have n elements then we have a potential of (n-1)! permutations. With n = 8 we have then 7! (=5040). Sattolo is then rejecting 87.5%.

Neither of them is cryptographic. However, if we were under attack, an attacker would be looking at brute forcing 40,320 permutations with Knuth and 5040 permutations with Sattolo. I'd put my money on Knuth.

The worldwide consensus is that Knuth is a shuffle - Sattolo is not. Disallowing an element to swap with itself is not a proper shuffle - it is called a derangement.

At the moment I cannot think of a reason why we should disallow an element swapping with itself, and I cannot find anyone advocating that in certain circumstances. Suppose we have six pointers, and we want to shuffle them such that no pointer remains unmoved. Sattolo will do the job. Why would anyone want to do that? I have no idea - but they have.

I don't know if Sattolo wrote a paper on his algorithm because if he did, I'd like to see it assuming that he gives a reason for using it.

With a deck of cards, we get 52! permutations with Knuth and 51! permutations with Sattolo. 51! is still a large number, but that gives a 98.07% rejection. That is many permutations being 'thrown out'.