Opgave

Implementeer Python-functies voor het genereren van permutaties van de lijst (1..n) in volgorde van minimale wijziging, volgens de Trotter-Johnson ordering (zie referentie):

• een functie permTrotterJohnsonRank die voor een gegeven waarde van n en een gegeven permutatie P de rank van P in de Trotter-Johnson ordering teruggeeft;
• een functie permTrotterJohnsonUnrank die voor een gegeven waarde van n en een gegeven waarde r de permutatie met rank r teruggeeft;
• een functie permTrotterJohnsonSuccessor die voor een gegeven waarde van n en een gegeven permutatie P de opvolger van P in de Trotter-Johnson ordering teruggeeft. Indien er geen opvolger meer is, geeft de functie "undefined" terug. Implementeer de expliciete successor-functie, m.a.w. doe geen default implementatie met gebruik van ranking- en unranking-functies.

Voorbeelden

>>> permTrotterJohnsonRank(4, [3, 4, 2, 1])
13
>>> permTrotterJohnsonUnrank(4, 13)
[3, 4, 2, 1]
>>> permTrotterJohnsonSuccessor(4, [3, 4, 2, 1])
[3, 2, 4, 1]

Referentie

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