Een reeks items kan van klein naar groot gesorteerd worden met een techniek die geïnspireerd is op het kaartspel Patience¹. Het sorteren gebeurt in twee stappen. Eerst worden de items één voor één in een reeks stapels gelegd volgens deze regels:

initieel zijn er geen stapels
het eerste item vormt een nieuwe stapel die enkel uit dat item bestaat
elk volgende item $$i$$ wordt bovenop de meest linkse stapel gelegd waarvan het bovenste item groter of gelijk is aan item $$i$$; als alle bovenste items kleiner zijn dan item $$i$$ dan wordt er rechts van de bestaande stapels een nieuwe stapel gevormd die enkel bestaat uit item $$i$$

Als alle items in een stapel gelegd zijn dan worden de items van klein naar groot gesorteerd door telkens het kleinste zichtbare item te kiezen. Hierbij liggen de zichtbare items bovenaan de stapels.

Stapels nadat alle items op een stapel gelegd zijn.

Stel bijvoorbeeld dat we aan de hand van deze techniek de reeks getallen (4 3 9 1 5 2 7 8 6) willen sorteren. De eerste stapel wordt gevormd door de getallen 4 en 3. Omdat 9 groter is dan 3, maken we voor 9 een tweede stapel. Daarna gaat 1 bovenop de eerste stapel, en gaan 5 en 2 bovenop de tweede stapel. Op dit punt bestaat de eerste stapel van boven naar beneden uit (1 3 4), de tweede stapel uit (2 5 9) en de resterende items uit (7 8 6). Nu gaat 7 op een derde stapel, 8 op een vierde stapel, en 6 gaat bovenop 7 in de derde stapel. Nu alle items in stapels gelegd zijn, wordt 1 verwijderd van de eerste stapel, 2 van de tweede stapel, 3 en 4 van de eerste stapel, 5 van de tweede stapel, 6 en 7 van de derde stapel, 8 van de vierde stapel en 9 van de tweede stapel.

Opgave

Een item wordt voorgesteld door een geheel getal (int). Een stapel items wordt voorgesteld als een lijst (list) waarvan het eerste element correspondeert met het bovenste item van de stapel en het laatste element met het onderste item van de stapel. Een reeks stapels die naast elkaar liggen wordt voorgesteld als een een lijst (list) waarvan het eerste element correspondeert met de stapel uiterst links en het laatste element met de stapel uiterst rechts.

Definieer een klasse PatienceSorteerder die kan gebruikt worden om een reeks items van klein naar groot te sorteren op basis van de techniek die geïnspireerd is op het kaartspel Patience. Bij het aanmaken van een object van de klasse PatienceSorteerder liggen er nog geen items in stapels. De klasse moet minstens de volgende methoden ondersteunen:

Een methode stapels die de reeks stapels (list) teruggeeft die er momenteel zijn.
Een methode aantal_stapels die teruggeeft hoeveel stapels (int) er momenteel zijn.
Een methode aantal_items die teruggeeft hoeveel items (int) er momenteel op alle stapels samen liggen.
Een methode item_toevoegen waaraan een item moet doorgegeven worden. Het gegeven item moet bovenop een (bestaande of nieuwe) stapel gelegd worden volgens de regels van de sorteertechniek die geïnspireerd is op het kaartspel Patience. De methode moet een verwijzing teruggeven naar het object waarop de methode werd aangeroepen.
Een methode items_toevoegen waaraan een reeks (list of tuple) items moet doorgegeven worden. De methode moet alle items uit de gegeven reeks één voor één bovenop een (bestaande of nieuwe) stapel leggen, volgens de regels van de sorteertechniek die geïnspireerd is op het kaartspel Patience. De methode moet een verwijzing teruggeven naar het object waarop de methode werd aangeroepen.
Een methode item_verwijderen waaraan geen argumenten moeten doorgegeven worden. Als er geen items meer zijn dan moet de methode een AssertionError opwerpen met de boodschap geen items meer. Anders moet de methode het kleinste zichtbare item van de stapels verwijderen. Als het kleinste zichtbare item bovenop meedere stapels ligt, dan moet de methode het item verwijderen uit de meest linkse van die stapels. Als het verwijderde item het laatste item was dat in de stapel lag, dan moet ook de stapel uit de reeks stapels verwijderd worden. De methode moet het verwijderde item teruggeven.
Een methode items_verwijderen waaraan geen argumenten moeten doorgegeven worden. De methode moet telkens het kleinste zichtbare item van de stapels verwijderen zoals dat bij de methode item_verwijderen gebeurt, totdat er geen items meer overblijven. De methode moet een tuple teruggeven met de items in de volgorde waarin ze verwijderd werden.

Voorbeeld

        >>> sorteerder = PatienceSorteerder()
>>> sorteerder.stapels()
[]
>>> sorteerder.aantal_stapels()
0
>>> sorteerder.item_toevoegen(4).stapels()
[[4]]
>>> sorteerder.aantal_stapels()
1
>>> sorteerder.item_toevoegen(3).stapels()
[[3, 4]]
>>> sorteerder.item_toevoegen(9).stapels()
[[3, 4], [9]]
>>> sorteerder.aantal_stapels()
2
>>> sorteerder.item_toevoegen(1).stapels()
[[1, 3, 4], [9]]
>>> sorteerder.item_toevoegen(5).stapels()
[[1, 3, 4], [5, 9]]
>>> sorteerder.item_toevoegen(2).stapels()
[[1, 3, 4], [2, 5, 9]]
>>> sorteerder.item_toevoegen(7).stapels()
[[1, 3, 4], [2, 5, 9], [7]]
>>> sorteerder.aantal_stapels()
3
>>> sorteerder.item_toevoegen(8).stapels()
[[1, 3, 4], [2, 5, 9], [7], [8]]
>>> sorteerder.item_toevoegen(6).stapels()
[[1, 3, 4], [2, 5, 9], [6, 7], [8]]
>>> sorteerder.aantal_stapels()
4
>>> sorteerder.aantal_items()
9
>>> sorteerder.item_verwijderen()
1
>>> sorteerder.stapels()
[[3, 4], [2, 5, 9], [6, 7], [8]]
>>> sorteerder.item_verwijderen()
2
>>> sorteerder.stapels()
[[3, 4], [5, 9], [6, 7], [8]]
>>> sorteerder.item_verwijderen()
3
>>> sorteerder.stapels()
[[4], [5, 9], [6, 7], [8]]
>>> sorteerder.item_verwijderen()
4
>>> sorteerder.stapels()
[[5, 9], [6, 7], [8]]
>>> sorteerder.aantal_stapels()
3
>>> sorteerder.item_verwijderen()
5
>>> sorteerder.stapels()
[[9], [6, 7], [8]]
>>> sorteerder.item_verwijderen()
6
>>> sorteerder.stapels()
[[9], [7], [8]]
>>> sorteerder.item_verwijderen()
7
>>> sorteerder.stapels()
[[9], [8]]
>>> sorteerder.item_verwijderen()
8
>>> sorteerder.stapels()
[[9]]
>>> sorteerder.item_verwijderen()
9
>>> sorteerder.stapels()
[]
>>> sorteerder.item_verwijderen()
Traceback (most recent call last):
AssertionError: geen items meer

>>> sorteerder = PatienceSorteerder()
>>> sorteerder.items_toevoegen([7, 5, 2, 1, 8, 6, 3, 9, 4]).stapels()
[[1, 2, 5, 7], [3, 6, 8], [4, 9]]
>>> sorteerder.aantal_stapels()
3
>>> sorteerder.aantal_items()
9
>>> sorteerder.items_verwijderen()
(1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> sorteerder.stapels()
[]
>>> sorteerder.aantal_stapels()
0
>>> sorteerder.aantal_items()
0

Bronnen

Burstein A, Lankham I (2006). Combinatorics of patience sorting piles. Séminaire Lotharingien de Combinatoire 54, B54Ab. ²
Chandramouli B, Goldstein J (2014). Patience is a virtue: revisiting merge and sort on modern processors. Proceedings of the 2014 ACM SIGMOD international conference on Management of data, 731–742. ³
Mallows C (1973). Patience sorting. Bulletin of the Institute of Mathematics and its Applications 9, 216–224.