A Million Random Digits with 100,000 Normal Deviates¹ is een boek dat in 1955 werd uitgebracht door de RAND Corporation². Het boek — dat zoals de titel reeds doet vermoeden hoofdzakelijk bestaat uit een tabel met een lange opeenvolging van willekeurig gegenereerde cijfers — was in de 20e eeuw belangrijk op het gebied van statistiek en willekeurige getallen. Het werd vanaf 1947 opgesteld door middel van een elektronische simulatie van een roulettewiel dat was aangesloten op een computer, en waarvan de resultaten vervolgens zorgvuldig gefilterd en getest werden vooraleer ze in de tabel konden opgenomen worden.

De RAND tabel betekende een belangrijke doorbraak in het werken met willekeurige getallen, aangezien een tabel van die omvang en toevalsgraad daarvoor niet voorhanden was. Naast de beschikbaarheid in boekvorm, konden de cijfers ook besteld worden op ponskaarten. De tabel werd hoofdzakelijk gebruikt in de statistiek en bij de experimentele opzet van wetenschappelijke experimenten, voornamelijk deze die gebruik maakten van zogenaamde Monte Carlo-simulaties³. Het boek was één van de laatste in een reeks tabellen met willekeurige getallen die geproduceerd werden vanaf het midden van de jaren '20 tot de jaren '50. Vanaf dan liet de opkomst van computers immers toe om op een snellere manier pseudowillekeurige getallen te genereren dan dat ze in tabellen konden opgezocht worden.

Het boek werd in 2001 heruitgegeven (ISBN 0-8330-3047-7) met een nieuw voorwoord van Michael D. Rich, Executive Vice President van de RAND Corporation. Het heeft sindsdien heel wat grappige commentaren gekregen op Amazon.com⁴:

• "I had a hard time getting into this book. The profanity was jarring and stilted, not at all how people really talk."

• "Once you get about halfway in, the rest of the story is pretty predictable."

• "If you like this book, I highly recommend that you read it in the original binary."

• "I would have given it five stars, but sadly there were too many distracting typos. For example: 46453 13987."

• "I really liked the '10034 56429 234088' part."

• "Frankly the sex scenes were awkward and clumsily written, adding very little of value to the plot."

• "For a supposedly serious reference work the omission of an index is a major impediment. I hope this will be corrected in the next edition."

De gemiddelde lezer geeft vier sterren aan het boek.

Voorbereiding

In de random module uit de Standard Python Library⁵ wordt een gegevenstype Random gedefinieerd, dat kan gebruikt worden om pseudo-toevallige keuzes te maken. Een computer kan immers nooit echt willekeurig werken, maar moet altijd een algoritme uitvoeren dat toeval simuleert. Dergelijke algoritmen berekenen bijvoorbeeld een volgende keuze op basis van een vorige keuze. De eerste keer dat er een keuze moet gemaakt worden, hebben deze algoritmen echter een vast vertrekpunt nodig omdat er dan nog geen vorige keuze was. Dat is de zogenaamde seed. Onderstaande voorbeeldsessie illustreert hoe het instellen van deze seed het maken van willekeurige keuzes kan beïnvloeden.

>>> karakters = 'UNCOPYRIGHTABLE'

>>> from random import Random
>>> generator = Random()

>>> [generator.choice(karakters) for _ in range(10)]
['E', 'Y', 'R', 'A', 'C', 'P', 'T', 'I', 'I', 'L']
>>> [generator.choice(karakters) for _ in range(10)]
['I', 'R', 'C', 'I', 'H', 'T', 'H', 'R', 'T', 'L']

>>> generator.seed(3)
>>> [generator.choice(karakters) for _ in range(10)]
['O', 'H', 'G', 'C', 'Y', 'E', 'H', 'I', 'T', 'H']
>>> [generator.choice(karakters) for _ in range(10)]
['N', 'H', 'U', 'E', 'L', 'I', 'P', 'G', 'O', 'O']

>>> generator.seed(3)
>>> [generator.choice(karakters) for _ in range(10)]
['O', 'H', 'G', 'C', 'Y', 'E', 'H', 'I', 'T', 'H']
>>> [generator.choice(karakters) for _ in range(10)]
['N', 'H', 'U', 'E', 'L', 'I', 'P', 'G', 'O', 'O']

>>> generator.seed(17)
>>> [generator.choice(karakters) for _ in range(10)]
['G', 'R', 'B', 'P', 'Y', 'P', 'C', 'B', 'A', 'A']
>>> [generator.choice(karakters) for _ in range(10)]
['G', 'T', 'P', 'N', 'E', 'U', 'O', 'R', 'L', 'A']

In eerste instantie wordt er een nieuw object van de klasse Random aangemaakt. Omdat er op dat moment nog geen seed werd opgegeven, wordt de systeemtijd (de tijd die de computer op zijn klok afleest) gebruikt als eerste seed. Daarna kan de methode choice gebruikt worden om een willekeurig element te kiezen uit een gegeven samengesteld object (in dit geval een willekeurig karakter uit de string UNCOPYRIGHTABLE).

Het instellen van een nieuwe seed gebeurt aan de hand van de seed methode. Aan deze methode kan elk (onveranderlijk) object doorgegeven worden, dat dan als nieuwe seed gebruikt wordt. De waarde None betekent dat opnieuw de systeemtijd als seed zal gebruikt worden. Als je goed kijkt naar de bovenstaande sessie, dan zal je zien dat het instellen van dezelfde seed als vertrekbasis (hier geïllustreerd aan de hand van de seed 3) ervoor zal zorgen dat dezelfde reeks keuzes zal gemaakt worden. Hierdoor kan je ervoor zorgen dat willekeurigheid in je programma's toch enigszins voorspelbaar verloopt.

Opgave

Definieer een klasse KarakterGenerator waarmee op een voorspelbare manier willekeurige reeksen karakters kunnen gegenereerd worden. Deze karakters worden willekeurig gekozen uit een opgegeven alfabet. Hiervoor moeten de objecten van de klasse KarakterGenerator minstens over de volgende methoden beschikken:

• Een initialisatiemethode waaraan een seed moet doorgegeven worden. Als seed mag elk (onveranderlijk) object doorgegeven worden, behalve de waarde None. Indien de waarde None wordt doorgegeven als seed, dan moet de initialisatiemethode een AssertionError opwerpen met de boodschap geen seed opgegeven. De initialisatiemethode moet ervoor zorgen dat elk object van de klasse KarakterGenerator beschikt over een eigen toevalsgenerator (een object van de klasse random.Random) en dat deze geïnitialiseerd wordt met de opgegeven seed. De initialisatiemethode heeft nog een tweede optionele parameter alfabet, waaraan een string van karakters kan doorgegeven worden. Dit vormt het alfabet van de karakters waaruit willekeurig zal moeten gekozen worden. Indien er geen expliciete waarde doorgegeven wordt voor de parameter alfabet, dan moet er gekozen worden uit de cijfers van het alfabet 0123456789.

• Een methode __repr__ die een stringvoorstelling van het object teruggeeft. Deze stringvoorstelling leest als een Python-expressie die een nieuw object aanmaakt van de klasse KarakterGenerator met dezelfde seed en hetzelfde alfabet als het huidige object. Bekijk onderstaande voorbeeldsessie om de verschillende vormen van deze stringvoorstelling te achterhalen. Let hierbij onder andere op het feit dat de optionele parameter enkel moet opgegeven worden indien het alfabet afwijkt van het standaardalfabet, en dat de parameter alfabet in dat geval expliciet moet benoemd worden.

• Een methode reset waaraan optioneel een seed kan doorgegeven worden. Indien een seed wordt doorgegeven aan de methode, dan wordt dit de nieuwe seed van het object. Daarna moet de seed van het object (hetzij de nieuwe, hetzij de oude waarde) gebruikt worden om de toevalsgenerator van het object opnieuw te initialiseren.

• Een methode reeks die een string teruggeeft bestaande uit een reeks willekeurig gekozen karakters. Hierbij moet de methode choice van de toevalsgenerator van het object aangeroepen worden, om telkens een willekeurig karakter te selecteren uit het alfabet van het object. Aan de methode reeks kan optioneel een argument doorgegeven worden (standaarwaarde: 1) dat de lengte van de string aangeeft die moet teruggegeven worden.

Voorbeeld

>>> cijfers = KarakterGenerator(3)
>>> cijfers
KarakterGenerator(3)

>>> cijfers.reeks()
'3'
>>> cijfers.reeks(19)
'9825979190748337887'
>>> cijfers.reeks(30)
'623286012904047966697251027346'

>>> cijfers.reset()
>>> cijfers
KarakterGenerator(3)
>>> cijfers.reeks(20)
'39825979190748337887'
>>> cijfers.reeks(30)
'623286012904047966697251027346'

>>> cijfers.reset(7)
>>> cijfers
KarakterGenerator(7)
>>> cijfers.reeks(20)
'52601815908301661318'
>>> cijfers.reeks(30)
'609139099603082462819482199351'

>>> KarakterGenerator(None)
Traceback (most recent call last):
AssertionError: geen seed opgegeven

>>> spam1 = KarakterGenerator(3, 'SPAM')
>>> spam2 = KarakterGenerator(3, 'SPAM')
>>> spam1.reeks(10)
'PPAMSSMAPP'
>>> spam2.reeks(10)
'PPAMSSMAPP'
>>> spam1
KarakterGenerator(3, alfabet='SPAM')