Try your algorithm with a smaller n first, instead of n=52, such as n=2 or n=3, ...

6nf · on Oct 1, 2016

Would you mind sharing your proof of this? I don't think you are correct. It seems to me that OP's algorithm is correct and will yield all permutations with equal probability.

All he's doing is picking a random card from the sorted deck and moving it to the top of the un-sorted deck. The sorted deck then becomes one card smaller.

For N = 2, In position 1 you choose card 1 with 50% and card 2 with 50% probability, and card 2 is just the remaining card. Thus

    p(12) = 50%
    p(21) = 50%

For N = 3, In position 1 you choose card 1 with p=1/3, card 2 with p=1/3, and card 3 with p=1/3:

    p(1xx) = 33% = 1/3
    p(2xx) = 33%
    p(3xx) = 33%

Then using the remaining 2 cards you just do the N=2 case from before, and so you have:

    p(123) = 50% x 33% = 1/6
    p(132) = 50% x 33%
    etc

conistonwater · on Oct 1, 2016

You're right, I think I misread the algorithm.

jbritton · on Oct 1, 2016

So I collected data for 100,000 runs

delta = (abs(count - mean) / mean) * 100.0

sd is standard deviation

>>> shuffle.test(100000, 2)

(0, 1) count: 50127, delta: 0.3%

(1, 0) count: 49873, delta: 0.3%

mean: 50000.0, sd: 179.6, sd/mean 0.4%

>>> shuffle.test(100000, 3)

(0, 1, 2) count: 16873, delta: 1.2%

(0, 2, 1) count: 16506, delta: 1.0%

(1, 0, 2) count: 16667, delta: 0.0%

(1, 2, 0) count: 16761, delta: 0.6%

(2, 0, 1) count: 16498, delta: 1.0%

(2, 1, 0) count: 16695, delta: 0.2%

mean: 16666.7, sd: 146.0, sd/mean 0.9%