Opgave

Implementeer Python-functies voor het genereren van deelverzamelingen van {1..n} geordend volgens stijgende cardinaliteit van de deelverzamelingen, en binnen eenzelfde cardinaliteit in lexicografische volgorde.

• een functie subsetSizeLexRank die voor een gegeven waarde van n en een gegeven deelverzameling T de rank van T teruggeeft;
• een functie subsetSizeLexUnrank die voor een gegeven waarde van n en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie subsetSizeLexSuccessor die voor een gegeven waarde van n en een gegeven deelverzameling T de opvolger van T in de gewenste ordening teruggeeft. Indien er geen opvolger meer is, geeft de functie "undefined" terug.

Voorbeelden

>>> subsetSizeLexRank(3, {2, 3})
6
>>> subsetSizeLexRank(8, {1, 3, 4, 5})
108
>>> subsetSizeLexUnrank(3, 6)
{2, 3}
>>> subsetSizeLexUnrank(8, 108)
{1, 3, 4, 5}
>>> subsetSizeLexSuccessor(3, {2, 3})
{1, 2, 3}
>>> subsetSizeLexSuccessor(3, {1, 2, 3})
"undefined"

Referentie

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