Implement a fair shuffle
Asked at Jane Street, HRT
Shuffle a list in place so that all orderings are equally likely, using only a uniform random integer generator.
A colleague proposes:
# WARNING: biased!
for i in range(n):
j = random.randint(0, n - 1) # swap with ANY position
items[i], items[j] = items[j], items[i]
Implement a correct uniform shuffle, and prove the colleague's version is biased.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.