79762926

Date: 2025-09-12 12:27:35
Score: 0.5
Natty:
Report link

Here is an alternative method of showing that this generates a uniform distribution of permutations.

Given a certain sequence of randint calls for Fisher-Yates, suppose we got the reversed sequence of calls for our modified algorithm.

The net effect is that we perform the swaps in reverse order. Since swaps are self-inverse, it follows that our modified algorithm produces the inverse permutation of the Fisher-Yates algorithm. Since every permutation has an inverse, it follows that the modified algorithm produces every permutation with equal probability.

(Incidentally, since rand() % N is not actually equiprobable (though the error is very slight for small N), this shows that both the standard FIsher-Yates algorithm and the modified algorithm are equally "bad", in that the set of probabilities for permutations is identical to each other (though this still assumes the PRNG is history-independent, but that's also not quite true).)

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (0.5):
Posted by: phenomist