Opgave

Implementeer Python-functies voor het genereren van k-deelverzamelingen van {1..n} in volgorde van minimale wijziging, volgens de revolving door ordering (zie referentie):

• een functie kSubsetRevDoorRank die voor gegeven waarden van n en k en een deelverzameling T (gegeven als een stijgende lijst van elementen) de rank van T in de revolving door ordering teruggeeft;
• een functie kSubsetRevDoorUnrank die voor gegeven waarden van n en k en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie kSubsetRevDoorSuccessor die voor gegeven waarden van n en k en een gegeven deelverzameling T de opvolger van T in de revolving door ordering teruggeeft. Indien er geen opvolger meer is, geeft de functie "undefined" terug. Implementeer een expliciete successor-functie, m.a.w. doe geen default implementatie met gebruik van ranking- en unranking-functies.

Voorbeelden

>>> kSubsetRevDoorRank(5, 3, [2, 4, 5])
5
>>> kSubsetRevDoorUnrank(5, 3, 5)
[2, 4, 5]
>>> kSubsetRevDoorSuccessor(5, 3, [2, 4, 5])
[3, 4, 5]

Referentie

• Donald L. Kreher en Douglas R. Stinson, “Combinatorial Algorithms: Generation, Enumeration and Search”, CRC Press, 1999 (hoofdstuk 2, paragraaf 2.3.3).