3 ms·
80% of the time they'll produce a subtly biased shuffle, most people don't intuitively know the fisher-yates method unless they've been taught it like, try thi
by kragen 3y ago
80% of the time they'll produce a subtly biased shuffle, most people don't intuitively know the fisher-yates method unless they've been taught it
like, try this
import collections, random
def shuffle(xs): # naive intuitive shuffle
for i in range(len(xs)):
j = random.randrange(len(xs))
xs[i], xs[j] = xs[j], xs[i]
def first_of(n):
xs = list(range(n))
shuffle(xs)
return xs[0]
print(collections.Counter([first_of(3) for i in range(100_000)]))
note that 1 comes out first 25% more often than 2, but with a fair shuffle all three should have an equal chance of being first
even without running it you can figure out logically that it must be biased in some way because there are 3! = 6 possible permutations and 3³ = 9 equally likely sequences of choices for j (each producing one of those permutations), and 9 is not divisible by 6, so some of those permutations have to be more likely than others
so i think this algorithm is a good one to get from a library if its randomness is important to you
not from chatgpt, which commonly does give you subtly buggy code
- kragen 3y agoi'm an idiot, 3³ = 27. but that's still not divisible by 6. that explains how it's possible to be only 25% more likely