2
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Nice catch Toby, vote up and mark your reply as answer. \$\endgroup\$ – Lin Ma Mar 5 '17 at 1:27
7
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ funny enough even the columns look like a bell-curve :) \$\endgroup\$ – Vogel612 Mar 2 '17 at 10:27
2
\$\begingroup\$

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]
\$\endgroup\$
  • 2
    \$\begingroup\$ Peilonrayz' and Toby Speight's answers illustrate that the second algoritm does not in fact uniformly distribute the cards, because it generally does not allow results from all of the permutations, since it doesn't consider the original element index as a possible insertion location. \$\endgroup\$ – Vogel612 Mar 2 '17 at 10:31
  • 1
    \$\begingroup\$ It was a bug in realization which was easy to fix. \$\endgroup\$ – Zefick Mar 2 '17 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.