Shuffling

A set of \(N\) distinct items can be arranged in \(N!\) different ways. We wish to write a computer program that shuffles the items randomly. Here are two candidates:

Code 1

1
2
3
for a = 1 to N-1
   for b = a+1 to N
      with 50% probability, swap item a and item b.

Code 2

1
2
3
for a = 1 to N-1
   b = uniformly chosen number between a+1 and N (inclusive).
   swap item a and item b.

Which of these codes, if any, will produce all \(N!\) possible arrangements with equal probabilities?

×

Problem Loading...

Note Loading...

Set Loading...