Opgave

Implementeer Python-functies voor het genereren van deelverzamelingen van {1..n} in volgorde van minimale wijziging, m.a.w. voor het genereren van Gray codes:

• een functie grayCodeRank die voor een gegeven waarde van n en een gegeven deelverzameling T de rank van T teruggeeft;
• een functie grayCodeUnrank die voor een gegeven waarde van n en een gegeven waarde r de deelverzameling met rank r teruggeeft;
• een functie grayCodeSuccessor die voor een gegeven waarde van n en een gegeven deelverzameling T de opvolger van T in de Gray code 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.

>>> grayCodeRank(8, {1, 2, 3, 4, 5, 7, 8})
173
>>> grayCodeUnrank(8, 173)
{1, 2, 3, 4, 5, 7, 8}
>>> grayCodeSuccessor(8, {1, 2, 3, 4, 5, 7, 8})
{1, 2, 3, 4, 5, 8}

Referentie

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