Opgave

Implementeer Python-functies voor het genereren van permutaties van de lijst [1,…,n] in lexicografische volgorde:

• een functie permLexRank die voor een gegeven waarde van n en een gegeven permutatie P de rank van P in de lexicografische volgorde teruggeeft;
• een functie permLexUnrank die voor een gegeven waarde van n en een gegeven waarde r de permutatie met rank r teruggeeft;
• een functie permLexSuccessor die voor een gegeven waarde van n en een gegeven permutatie P de opvolger van P 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.

Voorbeelden

>>> permLexRank(3, [2, 1, 3])
2
>>> permLexRank(4, [2, 4, 1, 3])
10
>>> permLexUnrank(3, 2)
[2, 1, 3]
>>> permLexUnrank(4, 10)
[2, 4, 1, 3]
>>> permLexSuccessor(3, [2, 1, 3])
[2, 3, 1]
>>> permLexSuccessor(3, [3, 2, 1])
"undefined"

Referentie

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