4 ms·

Is this a mathematically sound shuffle? It removes a random element from a sorted deck and then adds the element to a new deck. Python code below: import rando

Is this a mathematically sound shuffle? It removes a random element from a sorted deck and then adds the element to a new deck. Python code below: import random def shuffle(): random.seed() sorted_deck = range(52) # [0..51] shuffled_deck = [] slots_avail = 52 while slots_avail: idx = random.randint(0, slots_avail - 1) shuffled_deck.append(sorted_deck[idx]) del sorted_deck[idx] slots_avail -= 1 return shuffled_deck

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 ago
  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 10y ago
    You're right, I think I misread the algorithm.
- jbritton 10y ago
  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%
mattb314 10y ago
It looks correct to me, but keep in mind that deleting elements from the middle of an array is O(n), so overall your algorithm is O(n^2). You could fix this by always swapping your chosen element with the last element of the sorted_deck before removing it because removing from the end of an array is O(1).
jcranmer 10y ago
What you've described is essentially the Fisher-Yates shuffle implemented slowly (O(n²) implementation). The O(n) implementation would be: deck = range(52) for i in range(len(deck) - 1, 0, -1): j = random.randint(0, i) deck[i], deck[j] = deck[j], deck[i] Intuitively, what the latter implementation is doing is keeping the sorted_deck and shuffled_deck variables in the same array, moving the partition each iteration. The big problem with this method is that it is very easy to make a mistake in its implementation, and any slight mistake will lead to horribly biased outputs.
tuco86 10y ago
random.sample(range(52), 52)

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 ago
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 10y ago
  You're right, I think I misread the algorithm.
jbritton 10y ago
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%

mattb314 10y ago

It looks correct to me, but keep in mind that deleting elements from the middle of an array is O(n), so overall your algorithm is O(n^2). You could fix this by always swapping your chosen element with the last element of the sorted_deck before removing it because removing from the end of an array is O(1).

jcranmer 10y ago

What you've described is essentially the Fisher-Yates shuffle implemented slowly (O(n²) implementation). The O(n) implementation would be: deck = range(52) for i in range(len(deck) - 1, 0, -1): j = random.randint(0, i) deck[i], deck[j] = deck[j], deck[i] Intuitively, what the latter implementation is doing is keeping the sorted_deck and shuffled_deck variables in the same array, moving the partition each iteration. The big problem with this method is that it is very easy to make a mistake in its implementation, and any slight mistake will lead to horribly biased outputs.

tuco86 10y ago

random.sample(range(52), 52)