Two ways to randomly shuffle cards

Question

Here are two implementations I wrote to randomly shuffle cards.

• The first method (shuffle) selects a random card, then swaps it to the front.
• The second method (shuffle_v2) assumes that if i-1 cards are shuffled well, try to randomly swap card i with any card from 0 to i-1.

Are both methods are good to randomly (uniformly) shuffle cards?

Any ideas to improve time complexity, any code bugs or code style advice are also welcome.

import random
def shuffle(cards):
    write_index = 0 # to write,
    while write_index < len(cards):
        read_index = random.randint(write_index, len(cards)-1)
        cards[read_index], cards[write_index] = cards[write_index], cards[read_index]
        write_index += 1
def shuffle_v2(cards):
    for i in range(1, len(cards)):
        index = random.randint(0, i-1)
        cards[index], cards[i] = cards[i], cards[index]
if __name__ == "__main__":
    cards = []
    for i in range(10):
        cards.append(random.randint(1,52))
    print cards
    shuffle(cards)
    print cards
    shuffle_v2(cards)
    print cards

Answer 1

You have a bug in shuffle_v2, which is that you should consider all of [0..i] to be a candidate for the card at position i. As it is, your shuffle will never leave the last card in the last position. You can easily demonstrate this with a very small test-case (e.g. [0,1,2]).

A possible (but untested) fix:

def shuffle_v2(cards):
    for i in range(1, len(cards)):
        index = random.randint(0, i)
        if index != i:
            cards[index], cards[i] = cards[i], cards[index]

Answer 2

Add space between your functions, PEP8 suggests two spaces, but honestly any amount of space would be better than none.

There's not much of a difference between shuffle and shuffle_v2:

• You've written a for loop as a while loop. Which doesn't make much sense as Pythons for loops are really clean and easy to use.
• You use different bounds for your random.randint calls. shuffle is from the index to the end, for shuffle_v2 it's from the start to the index.

And so it's mostly asking which is better of the two different ranges. Using the following, we can find which is better:

import random
from collections import defaultdict, Counter


def shuffle(cards):
    for write_index in range(len(cards)):
        read_index = random.randrange(write_index, len(cards))
        cards[read_index], cards[write_index] = cards[write_index], cards[read_index]


def shuffle_v2(cards):
    for i in range(1, len(cards)):
        index = random.randrange(0, i)
        cards[index], cards[i] = cards[i], cards[index]

if __name__ == "__main__":
    data = list(range(7))
    count = defaultdict(int)
    bound = 1000000
    for fn in [shuffle, shuffle_v2]:
        count = defaultdict(int)
        for _ in range(bound):
            d = list(data)
            fn(d)
            count[tuple(d)] += 1
        print(len(count), Counter(count.values()))

Which resulted in:

5040 {146: 1,   152: 1,   154: 2,   155: 1,   157: 1,   158: 3,   159: 4,   160: 3,
      161: 5,   162: 5,   163: 1,   164: 4,   165: 9,   166: 10,  167: 9,   168: 10,
      169: 20,  170: 27,  171: 19,  172: 17,  173: 31,  174: 37,  175: 33,  176: 30,
      177: 50,  178: 54,  179: 35,  180: 53,  181: 75,  182: 64,  183: 77,  184: 85,
      185: 90,  186: 112, 187: 104, 188: 102, 189: 128, 190: 126, 191: 131, 192: 126,
      193: 165, 194: 140, 195: 131, 196: 150, 197: 134, 198: 152, 199: 152, 200: 126,
      201: 143, 202: 140, 203: 156, 204: 134, 205: 117, 206: 118, 207: 117, 208: 112,
      209: 102, 210: 101, 211: 98,  212: 87,  213: 85,  214: 69,  215: 58,  216: 62,
      217: 45,  218: 48,  219: 48,  220: 54,  221: 35,  222: 35,  223: 34,  224: 22,
      225: 22,  226: 22,  227: 22,  228: 22,  229: 9,   230: 10,  231: 10,  232: 13,
      233: 9,   234: 3,   235: 5,   236: 7,   237: 4,   238: 5,   239: 2,   240: 1,
      241: 1,   243: 2,   244: 1,   245: 2,   248: 1,   250: 1,   253: 1}

720 {1238: 1,  1284: 1,  1287: 1,  1290: 1,  1296: 2,  1300: 1,  1305: 1,  1306: 1,
     1308: 1,  1309: 1,  1310: 1,  1311: 1,  1313: 1,  1314: 2,  1315: 1,  1316: 2,
     1317: 1,  1318: 5,  1320: 3,  1322: 2,  1323: 1,  1324: 1,  1325: 1,  1326: 2,
     1327: 2,  1328: 1,  1329: 2,  1330: 1,  1331: 6,  1332: 1,  1333: 3,  1334: 1,
     1335: 1,  1336: 9,  1337: 2,  1338: 5,  1339: 3,  1340: 3,  1341: 3,  1342: 2,
     1343: 3,  1345: 6,  1346: 4,  1347: 2,  1348: 2,  1349: 1,  1350: 8,  1351: 7,
     1352: 1,  1353: 4,  1354: 4,  1355: 3,  1356: 5,  1357: 7,  1358: 7,  1359: 8,
     1360: 4,  1361: 4,  1362: 9,  1363: 4,  1364: 4,  1365: 10, 1366: 6,  1367: 2,
     1368: 6,  1369: 9,  1370: 8,  1371: 6,  1372: 9,  1373: 9,  1374: 7,  1375: 8,
     1376: 8,  1377: 5,  1378: 10, 1379: 10, 1380: 5,  1381: 14, 1382: 8,  1383: 7,
     1384: 7,  1385: 4,  1386: 7,  1387: 10, 1388: 11, 1389: 6,  1390: 11, 1391: 2,
     1392: 7,  1393: 10, 1394: 4,  1395: 5,  1396: 12, 1397: 7,  1398: 10, 1399: 8,
     1400: 6,  1401: 8,  1402: 6,  1403: 5,  1404: 7,  1405: 7,  1406: 5,  1407: 14,
     1408: 8,  1409: 7,  1410: 5,  1411: 2,  1412: 2,  1413: 6,  1414: 6,  1415: 6,
     1416: 4,  1417: 10, 1418: 14, 1419: 8,  1420: 5,  1421: 4,  1422: 4,  1423: 3,
     1424: 6,  1425: 2,  1426: 9,  1427: 3,  1428: 6,  1429: 4,  1430: 4,  1431: 6,
     1432: 1,  1433: 4,  1434: 3,  1435: 2,  1436: 2,  1437: 1,  1438: 3,  1439: 1,
     1440: 2,  1441: 2,  1442: 2,  1443: 1,  1444: 4,  1445: 5,  1446: 2,  1447: 4,
     1448: 4,  1449: 3,  1450: 4,  1452: 2,  1453: 1,  1454: 1,  1455: 1,  1458: 1,
     1459: 3,  1460: 2,  1462: 1,  1463: 1,  1464: 1,  1465: 1,  1466: 2,  1467: 1,
     1468: 2,  1471: 2,  1472: 3,  1473: 1,  1476: 2,  1478: 1,  1483: 1,  1485: 1,
     1508: 1,  1531: 1}

This shows that the first algorithm not only had a more uniform distribution, it can actually shuffle into all 5040 different permutations. And so is the superior algorithm.

Answer 3

First algorithm is 100% right. My analysis: position with index 1 can be occupied by any element with equal probability, position 2 - any from rest elements. We can calculate that any element can be placed on position 2 with equal probability and so on. So the shuffling is uniform.

Second case a bit difficult but len's try to proof by induction. The lements distributed uniformly after first step (50/50). If elements distributed uniformly after n steps then after step n+1 it can be found:

• In position n+1 with probability 1/(n+1) because of random swapping

• In any other position with probability 1/n * (n/(n+1))) if it wasn't swapped which is equal to 1/(n+1) again!

So this shuffling is uniform too.

I would write shuffle_v1 to look more like shuffle_v2 for consistency:

def shuffle(cards):
    for i in range (0, len(cards)-1):
        index = random.randint(i, len(cards)-1)
        cards[index], cards[i] = cards[i], cards[index]