Kies uit een standaard kaartspel evenveel zwarte als rode kaarten (je mag ook het volledige kaartspel nemen), en maak daarmee een stapel waarbij de kaarten afwisselend rood en zwart zijn. Het maakt niet uit of de bovenste kaart zwart of rood is. Splits nu de stapel kaarten in twee kleinere stapels die ongeveer even hoog zijn, maar zorg ervoor dat de onderste kaart van de ene stapel zwart is en de onderste kaart van de andere rood. Dit kan alleen als de twee stapels een oneven aantal kaarten bevatten, waardoor meteen ook de bovenste en de onderste kaart van elke stapel een andere fysieke kleur moeten hebben.

Til de twee kleinere stapels met de duimen omhoog en laat de kaarten willekeurig op elkaar vallen: eerst een paar kaarten van de eerste stapel, dan een paar kaarten van de tweede stapel, dan weer een paar kaarten van de eerste stapel, …, totdat alle kaarten van de twee stapels in elkaar gevallen zijn. Schuif nu alle kaarten samen tot een nieuwe stapel. Deze manier om de kaarten te schudden wordt de zwaluwstaartmethode¹ (Engels: riffle-shuffle) genoemd. Neem nu telkens twee kaarten van de bovenkant van de nieuwe stapel. Hoeveel van die paren zullen er een verschillende fysieke kleur hebben (één zwarte kaart en één rode kaart)?

Kaarten schudden volgens de zwaluwstaartmethode.

Verrassend genoeg zullen alle paren een verschillende fysieke kleur hebben. Veronderstel bijvoorbeeld dat er eerst een zwarte kaart valt. Dan moet die ofwel gevolgd worden door de volgende kaart van dezelfde stapel (die een rode kleur heeft) of de eerste kaart van de andere stapel (die ook een rode kleur heeft). Hoe dan ook zal het eerste paar bestaan uit één zwarte en één rode kaart. Als we dezelfde redenering doortrekken, dan zal dat ook gelden voor alle andere paren opeenvolgende kaarten in de stapel die we na het schudden bekomen hebben. Dit fenomeen werd voor het eerst ontdekt in 1958 door de goochelaar Norman Gilbreath.

Opgave

Een standaard kaartspel bestaat uit 52 verschillende kaarten die onderverdeeld worden in vier kleuren van elk 13 kaarten: 13 klaveren (♣), 13 ruiten (♦), 13 harten (♥) en 13 schoppen (♠). Klaveren en schoppen zijn zwart, ruiten en harten zijn rood, maar het zijn niet deze fysieke kleuren, maar de soorten die met de term kleur aangeduid worden. Van elke kleur zijn er telkens kaarten met een rang van 2 tot en met 10, een boer, een vrouw, een heer en een aas. Daarnaast bevat een spel soms twee of drie jokers, maar die laten we hier even buiten beschouwing.

We beschrijven elk van de 52 kaarten van een standaard kaartspel met een string (str) die bestaat uit de rang van de kaart, gevolgd door de kleur van de kaart:

rangen: 2, 3, 4, 5, 6, 7, 8, 9, 10, J (boer), Q (vrouw), K (heer) en A (aas)
kleuren: C (klaveren; ♣), D (ruiten; ♦), H (harten; ♥) en S (schoppen; ♠)

Zo stelt AS bijvoorbeeld schoppenaas voor, 10H hartentien en KC klaverenheer.

We stellen een stapel kaarten voor als een lijst (list) met de beschrijvingen van de kaarten uit de stapel, waarbij de bovenste kaart van de stapel het eerste element van de lijst is. Een stapel hoeft niet noodzakelijk alle 52 kaarten van een kaartspel te bevatten.

Bij de zwaluwstaartmethode vallen alle kaarten van een stapel in groepen van een aantal opeenvolgende kaarten. We stellen zo een gegroepeerde stapel voor als een lijst (list) waarin alle kaarten gegroepeerd zijn in tuples (tuple). Hierbij stelt de buitenste lijst de stapel voor, en de tuples met kaarten in die lijst stellen de groepen voor. Zo stelt

        [('KS', '4H'), ('KH', 'JD'), ('10S', '2D'), ('9C', 'JH')]

een gegroepeerde stapel voor waarvan de kaarten gegroepeerd zijn in vier groepen van twee kaarten. Als we de acht kaarten uit die stapel groeperen in drie groepen met respectievelijk 2, 4 en 2 kaarten, dan wordt dit voorgesteld door de gegroepeerde stapel

        [('KS', '4H'), ('KH', 'JD', '10S', '2D'), ('9C', 'JH')]

De zwaluwstaartmethode werkt dan met twee gegroepeerde stapels die evenveel groepen bevatten, maar waarvan de groepen niet noodzakelijk evenveel kaarten moeten bevatten. Het resultaat van de zwaluwstaartmethode is een nieuwe stapel die gevormd wordt door de kaarten van de eerste groep van de eerste stapel, gevolgd door de kaarten van de eerste groep van de tweede stapel, gevolgd door de kaarten van de tweede groep van de eerste stapel, gevolgd door de kaarten van de tweede groep van de tweede stapel, …

Gevraagd wordt:

Schrijf een functie groepeer waarmee we een stapel kaarten in groepen kunnen verdelen. Aan de functie moeten twee argumenten doorgegeven worden: i) een stapel kaarten en ii) een omschrijving van de grootte van elke groep. Deze omschrijving kan zowel een natuurlijk getal (int) als een reeks (list of tuple) natuurlijke getallen (int) zijn. Als de omschrijving een getal $$n \in \mathbb{N}_0$$ is, dan moeten de kaarten van de stapel verdeeld worden in groepen die allemaal $$n$$ kaarten bevatten. Als de omschrijving een reeks $$(s_1, s_2, \ldots, s_m)$$ is met $$s_i \in \mathbb{N}_0 (i=1, \ldots, m)$$, dan moeten de kaarten van de stapel verdeeld worden in groepen van respectievelijk $$s_1, s_2, \ldots, s_m$$ kaarten. De functie moet de gegroepeerde stapel teruggeven. Als de omschrijving geen int is of geen list/tuple van ints, of als de stapel kaarten niet in groepen kan verdeeld worden volgens de omschrijving van de grootte van elke groep, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige groepering.
Schrijf een functie zwaluwstaart waaraan twee gegroepeerde stapels kaarten moeten doorgegeven worden. De stapels moeten evenveel groepen bevatten. Als dat niet het geval is dan moet de functie een AssertionError opwerpen met de boodschap verschillend aantal groepen. Anders moet de functie de stapel kaarten teruggeven die we bekomen als we de zwaluwstaartmethode toepassen op de twee gegroepeerde stapels.
Schrijf een functie gemengde_paren waaraan een stapel met een even aantal kaarten moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of alle paren bestaan uit een rode en een zwarte kaart (de volgorde speelt geen rol) als we telkens de twee bovenste kaarten van de stapel nemen. Als de stapel bestaat uit een oneven aantal kaarten, dan moet een AssertionError opgeworpen worden met de boodschap oneven aantal kaarten.

Geen enkele van deze functies mag haar argumenten wijzigen.

Voorbeeld

        >>> kaarten = ['KS', '4H', 'KH', 'JD', '10S', '2D', '9C', 'JH']
>>> groepeer(kaarten, 2)
[('KS', '4H'), ('KH', 'JD'), ('10S', '2D'), ('9C', 'JH')]
>>> groepeer(kaarten, 4)
[('KS', '4H', 'KH', 'JD'), ('10S', '2D', '9C', 'JH')]
>>> groepeer(kaarten, 3)
Traceback (most recent call last):
AssertionError: ongeldige groepering
>>> groepeer(kaarten, [2, 4, 2])
[('KS', '4H'), ('KH', 'JD', '10S', '2D'), ('9C', 'JH')]
>>> groepeer(kaarten, (3, 2, 3))
[('KS', '4H', 'KH'), ('JD', '10S'), ('2D', '9C', 'JH')]
>>> groepeer(kaarten, [3, 1, 3])
Traceback (most recent call last):
AssertionError: ongeldige groepering

>>> stapel1 = [('7C', '2D', 'JC'), ('7H', '10S', '9D'), ('5C', 'AH', '3C')]
>>> stapel2 = [('AD', '9C'), ('KD', '10C', 'QH', 'JS'), ('4D', 'AS', '8D')]
>>> stapel3 = [('AD',), ('9C', 'KD', '10C'), ('QH', 'JS'), ('4D', 'AS', '8D')]
>>> zwaluwstaart(stapel1, stapel2)
['7C', '2D', 'JC', 'AD', '9C', '7H', '10S', '9D', 'KD', '10C', 'QH', 'JS', '5C', 'AH', '3C', '4D', 'AS', '8D']
>>> zwaluwstaart(stapel1, stapel3)
Traceback (most recent call last):
AssertionError: verschillend aantal groepen

>>> nieuwe_stapel = zwaluwstaart(stapel1, stapel2)
>>> gemengde_paren(nieuwe_stapel)
True
>>> gemengde_paren(['7C', '2D', 'JC', '7H', '10S', '9D', '5C', 'AH', '3C'])
Traceback (most recent call last):
AssertionError: oneven aantal kaarten

Bronnen

Gardner M (August 1960). Mathematical Recreation column. Scientific American.
Gardner M (1966). New Mathematical Diversions from Scientific American.
Gilbreath N (1958). Magnetic colors. The Linking Ring 38(5), 60.