Opgave

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

• een functie subsetLexRank die voor een gegeven waarde van n en een gegeven deelverzameling T de rank van T teruggeeft;
• een functie subsetLexUnrank die voor een gegeven waarde van n en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie subsetLexSuccessor die voor een gegeven waarde van n 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.

Voorbeelden

>>> subsetLexRank(3, {2, 3})
3
>>> subsetLexRank(8, {1, 3, 4, 6})
180
>>> subsetLexUnrank(3, 3)
{2, 3}
>>> subsetLexUnrank(8, 180)
{1, 3, 4, 6}
>>> subsetLexSuccessor(3, {2, 3})
{1}
>>> subsetLexSuccessor(3, {1, 2, 3})
"undefined"

Referentie

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