Obscure random.shuffle() note

[ichabod801]

So, I'm working on a game suite which includes card games. So I need to shuffle decks of cards. The obvious thing to do is create the decks as lists of cards and use random.shuffle(). Now, I remember hearing back in the day that the early poker websites had problems because their random number generators had a period that was smaller than the number of possible deck orderings (52!). So some shuffles never occurred, and that fact could be exploited. The documentation for random.python() even has a note on that:

Output:
Note that for even rather small len(x), the total number of permutations of [i]x[/i] is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

Before checking here for alternative random number generators, I checked 52!

Output:
80658175170943878571660636856403766975289505440883277824000000000000

against the period of the Mersenne Twister, the PRNG used by random.shuffle(), which is 2 ** 19937 - 1:

Output:
43154247973881626480552355163379198390539350432267115051652505414033306801376580911304513629318584665545269938257648835317902217334584413909528269154609168019007875343741396296801920114486480902661414318443276980300066728104984095451588176077132969843762134621790396391341285205627619600513106646376648615994236675486537480241964350295935168662363909047948347692313978301377820785712419054474332844529183172973242310888265081321626469451077707812282829444775022680488057820028764659399164766265200900561495800344054353690389862894061792872011120833614808447482913547328367277879565648307846909116945866230169702401260240187028746650033445774570315431292996025187780790119375902863171084149642473378986267503308961374905766340905289572290016038000571630875191373979555047468154333253474991046248132504516341796551470575481459200859472614836213875557116864445789750886277996487304308450484223420629266518556024339339190844368921018424844677042727664601852914925277280922697538426770257333928954401205465895610347658855386633902546289962132643282425748035786233580608154696546932563833327670769899439774888526687278527451002963059146963875715425735534475979734463100678367393327402149930968778296741391514599602374213629898720611431410402147238998090962818915890645693934483330994169632295877995848993366747014871763494805549996163051541225403465297007721146231355704081493098663065733677191172853987095748167816256084212823380168625334586431254034670806135273543270714478876861861983320777280644806691125713197262581763151313596429547763576367837019349835178462144294960757190918054625114143666384189433852576452289347652454631535740468786228945885654608562058042468987372436921445092315377698407168198376538237748614196207041548106379365123192817999006621766467167113471632715481795877005382694393400403061700457691135349187874888923429349340145170571716181125795888889277495426977149914549623916394014822985025331651511431278802009056808456506818877266609831636883884905621822262933986548645669080672191704740408891349835685662428063231198520436826329415290752972798343429446509992206368781367154091702655772727391329424277529349082600585884766523150957417077831910016168475685658673192860882070179760307269849987354836042371734660257694347235506301744118874141292438958141549100609752216882230887611431996472330842380137110927449483557815037586849644585749917772869926744218369621137675101083278543794081749094091043084096774144708436324279476892056200427227961638669149805489831121244676399931955371484012886360748706479568669048574782855217054740113945929622177502575565811067452201448981991968635965361551681273982740760138899638820318776303668762730157584640042798880691862640268612686180883874939573818125022279689930267446255773959542469831637863000171279227151406034129902181570659650532600775823677398182129087394449859182749999007223592423334567850671186568839186747704960016277540625331440619019129983789914712515365200336057993508601678807687568562377857095255541304902927192220184172502357124449911870210642694565061384919373474324503966267799038402386781686809962015879090586549423504699190743519551043722544515740967829084336025938225780730880273855261551972044075620326780624448803490998232161231687794715613405793249545509528052518010123087258778974115817048245588971438596754408081313438375502988726739523375296641615501406091607983229239827240614783252892479716519936989519187808681221191641747710902480633491091704827441228281186632445907145787138351234842261380074621914004818152386666043133344875067903582838283562688083236575482068479639546383819532174522502682372441363275765875609119783653298312066708217149316773564340379289724393986744139891855416612295739356668612658271234696438377122838998040199739078061443675415671078463404673702403777653478173367084844734702056866636158138003692253382209909466469591930161626097920508742175670306505139542860750806159835357541032147095084278461056701367739794932024202998707731017692582046210702212514120429322530431789616267047776115123597935404147084870985465426502772057300900333847905334250604119503030001704002887892941404603345869926367501355094942750552591581639980523190679610784993580896683299297681262442314008657033421868094551740506448829039207316711307695131892296593509018623094810557519560305240787163809219164433754514863301000915916985856242176563624771328981678548246297376249530251360363412768366456175077031977457534912806433176539995994343308118470147158712816149394421276614228262909950055746981053206610001560295784656616193252269412026831159508949671513845195883217147982748879261851417819979034417285598607727220866677680426090308754823803345446566305619241308374452754668143015487710877728011086004325892262259413968285283497045571062757701421761565262725153407407625405149931989494459106414660534305378576709862520049864880961144869258603473714363659194013962706366851389299692869491805172556818508298824954954815796063169517658741420159798754273428026723452481263569157307213153739781041627653715078598504154797287663122946711348158529418816432825044466692781137474494898385064375787507376496345148625306383391555145690087891955315994462944493235248817599907119135755933382121706191477185054936632211157222920331148502487563303118018805685073569841580518118710778653953571296014372940865270407021924383167290323231567912289419486240594039074452321678019381871219092155460768444573578559513613304242206151356457513937270939009707237827101245853837678338161023397586854894230696091540249987907453461311923963852950754758058205625956600817743007191746812655955021747670922460866747744520875607859062334750627098328593480067789456169602494392813763495657599847485773553990957557313200809040830036446492219409934096948730547494301216165686750735749555882340303989874672975455060957736921559195480815514035915707129930057027117286252843197413312307617886797506784260195436760305990340708481464607278955495487742140753570621217198252192978869786916734625618430175454903864111585429504569920905636741539030968041471

Okay. So, not a problem.

But, Blackjack is one of the games I will be implementing. Blackjack often using multiple deck shoes, ATW up to eight decks in a shoe. So I began to wonder when it would become a problem:

>>> period = 2 ** 19937 - 1
>>> length = 1
>>> multiplier = 1
>>> while length < period:
...     multiplier += 1
...     length *= multiplier
... 
>>> multiplier
2081

So, as long as your list is less than 2,081 items, you're good to go with random.shuffle (barring the other caveats in the documentation on the random module). Just another bit of mostly useless information brought to you by a guy needing a break from doing QC at work.

[micseydel]

That's actually interesting, thanks for sharing! Though the probability of this being a problem is low, it's definitely good to keep in the back of our minds.

[ichabod801]

I could see it being a problem. If I was using Python to analyze the data we use at work, and wanted to take a random sample for jack knifing or something, it would definitely be something to think about.

[micseydel]

Ah, good point. For my work, it might be less likely, but the data science team very well may have it come up. (Or even testing, to your point about QA.)