Opgave

Implementeer Python-functies voor het genereren van k-deelverzamelingen van {1..n} in lexicografische en co-lexicografische volgorde:

• een functie kSubsetLexRank 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 lexicografische volgorde teruggeeft;
• een functie kSubsetLexUnrank die voor gegeven waarden van n en k en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie kSubsetLexSuccessor die voor gegeven waarden van n en k en een gegeven deelverzameling T de opvolger van T in de lexicografische volgorde 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.
• een functie kSubsetColexRank die voor gegeven waarden van n en k en een deelverzameling T’ (gegeven als een dalende lijst van elementen) de rank van T’ in de co-lexicografische volgorde teruggeeft;
• een functie kSubsetColexUnrank die voor gegeven waarden van n en k en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie kSubsetColexSuccessor die voor gegeven waarden van n en k en een gegeven deelverzameling T’ de opvolger van T in de co-lexicografische volgorde 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

>>> kSubsetLexRank(5, 3, [1, 2, 5])
2
>>> kSubsetLexUnrank(5, 3, 2)
[1, 2, 5]
>>> kSubsetLexSuccessor(5, 3, [1, 2, 5])
[1, 3, 4]
>>> kSubsetLexSuccessor(5, 3, [3, 4, 5])
"undefined"
>>> kSubsetColexRank(5, 3, [4, 3, 2])
3
>>> kSubsetColexUnrank(5, 3, 3)
[4, 3, 2]
>>> kSubsetColexSuccessor(5, 3, [4, 3, 2])
[5, 2, 1]

Referentie

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