“Op elk potje past een dekseltje” luidt het spreekwoord. Dit wordt vooral gebruikt bij iemand die tegenslag in de liefde ondervindt, om hem of haar een hart onder de riem te steken en zodoende de hoop op het vinden van een geschikte levenspartner in stand te houden.

In deze opgave zetten we dit spreekwoord om in de praktijk: gegeven een verzameling potjes en een verzameling deksels, stellen we een verzameling van koppels op. Voor elk potje is er minstens één passend dekseltje en omgekeerd, maar helaas zijn deze door elkaar geraakt. Natuurlijk zouden we voor elk potje alle deksels kunnen overlopen om zo een passend koppel te vormen, maar we willen graag sneller te werk gaan. We zouden bijvoorbeeld beide verzamelingen kunnen sorteren met een efficiënt algoritme (twee keer gemiddelde tijdscomplexiteit \(\Theta(s \times log(s))\) met \(s\) het aantal potjes en deksels) en ze dan gewoon twee-aan-twee koppelen. Eén probleem: je kan een potje niet zomaar met andere potjes vergelijken, en een deksel niet met andere deksels.

Om dit probleem efficiënt op te lossen halen we onze inspiratie bij het QuickSort-algoritme. We kunnen namelijk als spil een potje uitkiezen en hiermee de deksels verdelen in drie groepen:

De deksels die te klein zijn voor het gekozen referentiepotje.
De deksels die precies op dit potje passen (zo is er steeds minstens één).
Alle deksels die te groot zijn voor dit potje.

Vervolgens nemen we een deksel uit de tweede groep om ook de potjes op dezelfde manier op te splitsen. Na het uitvoeren van deze twee complementaire stappen hebben we reeds een of meerdere allemaal even grote potjes en deksels gevonden die precies op elkaar passen, en bovendien hebben we de resterende potjes onderverdeeld in kleine en grote exemplaren, die we recursief verder kunnen opsplitsen volgens dezelfde strategie.

Aan jullie om dit algoritme zorgvuldig uit te werken en te implementeren. Net zoals bij het originele QuickSort-algoritme maak je best geen nieuwe lijsten voor de drie groepen, maar partitioneer je de lijst in place door de potjes en deksels te herordenen via opeenvolgende verwisselingen.

Opgave

Schrijf de functie match(jars: list, lids: list, cmp). Gegeven twee even lange lijsten jars en lids met respectievelijk potjes en dekseltjes, geef je een (opnieuw even lange) lijst van koppels terug. Elk koppel tuple(potje, deksel) bevat een passend potje en deksel. Elk gegeven potje en dekseltje komt precies eenmaal voor in één enkel koppel in de uitvoer.

Voorbeelden

>>> match([3], [1, 3], lambda x, y: x - y)
>>> match([],[], lambda x, y: x - y)
[]
>>> match([1], [1], lambda x, y: x - y)
[(1, 1)]
>>> match([3, 1, 2], [1, 2, 3], lambda x, y: x - y)
[(1, 1), (2, 2), (3, 3)]
>>> match([1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], lambda x, y: x - y)
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]
>>> match([1, 2, 3, 3, 2, 1], [1, 2, 3, 3, 2, 1], lambda x, y: x - y)
[(1, 1), (1, 1), (2, 2), (2, 2), (3, 3), (3, 3)]
>>> match([63, 5, 25, 19, 93, 82, 48, 70, 18, 84], [63, 5, 25, 19, 93, 82, 48, 70, 18, 84], lambda x, y: x - y)
[(5, 5), (18, 18), (19, 19), (25, 25), (48, 48), (63, 63), (70, 70), (82, 82), (84, 84), (93, 93)]
>>> match([4, 5, 6, 7, 8], [3, 4, 5, 6, 7], lambda x, y: x - 1 - y)
[(4, 3), (5, 4), (6, 5), (7, 6), (8, 7)]