Card Shuffler

The answer might be counter-intuitive at first. Why is Bob's algorithm bad? Couldn't it generate all permutations? The answer is yes; it could generate all permutations, but not evenly. There is a total of $n^n$ moves, but there are only $n!$ permutations. Since $n!$ doesn't divide $n^n$ in general, not all permutations have equal chance to be generated.

Now we are convinced that Bob's algorithm is bad, but how bad it is? Noticed that if a card is swapped to its left, it couldn't go left any further!

Still not convinced? Let the data do the speaking.

The left image is Alice's algorithm and the right one is Bob's. The x-axis is the numbers, and the y-axis is the position it ended up after going through the algorithm. The brighter the cell, the higher frequency the number ended up in that position. As you can see, most of the numbers ended up being on its left!

If you are interested in how the visualisation is generated, here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

from random import randint
import matplotlib.pyplot as plt

x_data = []
y_data = []
# start simultion for distributed permutations
for simulation in range(1000):
    # perfectly sorted array
    arr = [x + 1 for x in range(1000)]
    for i in range(1000):
        r = randint(0, i) # correct way

        # swap two elements
        arr[r], arr[i] = arr[i], arr[r]

    # collect result
    for i in range(1000):
        x_data.append(arr[i])
        y_data.append(i+1)
# end simulation

# plot
fig, axs = plt.subplots(ncols = 2, sharey=True, figsize=(14, 6))
fig.subplots_adjust(hspace=0.5, left=0.07, right=0.93)
hb = axs[0].hexbin(x_data, y_data, gridsize=50, cmap='inferno')
axs[0].axis([0, 1000, 0, 1000])
axs[0].set_title("Distributed Permutation")
cb = fig.colorbar(hb, ax=axs[0])
cb.set_label('frequency')

x_data = []
y_data = []
# start simultion for biased permutations
for simulation in range(1000):
    # perfectly sorted array
    arr = [x + 1 for x in range(1000)]
    for i in range(1000):
        r = randint(0,999) # wrong way

        # swap two elements
        arr[r], arr[i] = arr[i], arr[r]

    # collect result
    for i in range(1000):
        x_data.append(arr[i])
        y_data.append(i+1)
# end simulation

# plot
fig.subplots_adjust(hspace=0.5, left=0.07, right=0.93)
hb = axs[1].hexbin(x_data, y_data, gridsize=50, cmap='inferno')
axs[1].axis([0, 1000, 0, 1000])
axs[1].set_title("Biased Permutation")
cb = fig.colorbar(hb, ax=axs[1])
cb.set_label('frequency')

plt.show()