This is cute.
As the above makes clear, you are basically making random coin flips until it spits out an answer. If the array has n entries, there is some maximum number of flips, say k, that you could be asked for.
Turning it around on its head I could just ask you up front to make k coin flips, then feed that into the algorithm, and get an answer. Now there are 2^k possible sequences that you could give me, and they are all equally likely. So if you write in base 2, the probability of any particular permutation is 2^(-k) times the number of sequences that gave that permutation.
What that is I don't care. What I do care about is that when written out in base 2 that probability is a decimal that terminates after at most k places. But for each permutation the probability we really want is 1/n!, and if n is bigger than 2 then n! is divisible by 3 which is *not* a power of two so 1/n! has to be (base 2) an infinite repeating decimal!
In other words I may not, without calculating it, have any idea how your anwer will be biased, but in fact it is!
ObTrivia: A somewhat similar counting argument manages to show that the 400 year Gregorian calendar repeats days of the week, but cannot divide a particular day of the month between them. However it takes explicit calculation to show that the 13'th falls on Friday more than 1 day in 7.
In reply to (tilly) (still imperfect): Randomize an array
by tilly
in thread Randomize an array
by Zebu
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |