4 ms·
Try your algorithm with a smaller n first, instead of n=52, such as n=2 or n=3, and slots_avail=n. For n=3 it generates the permutation {1,2,3} with probabilit
by conistonwater 10y ago
Try your algorithm with a smaller n first, instead of n=52, such as n=2 or n=3, and slots_avail=n.
For n=3 it generates the permutation {1,2,3} with probability that is 11% higher than the correct probability.
- 6nf 10y agoWould 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 10y agoYou're right, I think I misread the algorithm.
- jbritton 10y agoSo 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%