Opgave

Implementeer Python-functies voor het genereren van partities van het gehele getal n in k delen, waarbij de delen verschillend zijn, in omgekeerde lexicografische volgorde van de standard form (zie referentie):

• een functie genereerPartities die voor gegeven waarden van n en k een lijst van alle partities van n in k verschillende delen teruggeeft;
• een functie telPartities die voor gegeven waarden van n en k het aantal partities van n in k verschillende delen teruggeeft;
• een functie partitieLexSuccessor die voor gegeven waarden van n en k en een gegeven partitie P de opvolger van P in de lexicografische volgorde teruggeeft. Indien er geen opvolger meer is, geeft de functie "undefined" terug;
• [optioneel] een functie partitieLexRank die voor gegeven waarden van n en k en een gegeven partities P de rank van P in de lexicografische volgorde teruggeeft (hiervoor mag je een eenvoudige implementatie geven die gebruik maakt van genereerPartities);
• [optioneel] een functie partitieLexUnrank die voor gegeven waarden van n en k en een gegeven waarde r de partitie met rank r teruggeeft (hiervoor mag je een eenvoudige implementatie geven die gebruik maakt van genereerPartities);

Voorbeelden

>>> genereerPartities(5, 2)
[[4, 1], [3, 2]]
>>> genereerPartities(8, 3)
[[5, 2, 1], [4, 3, 1]]
>>> genereerPartities(16, 4)
[[10, 3, 2, 1], [9, 4, 2, 1], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 2, 1], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2]]
>>> telPartities(5, 2)
2
>>> telPartities(8, 3)
2
>>> telPartities (16, 4)
9
>>> partitieLexRank(16, 4, [8, 4, 3, 1])
3
>>> partitieLexUnrank(16, 4, 3)
[8, 4, 3, 1]
>>> partitieLexSuccessor(16, 4, [8, 4, 3, 1])
[7, 6, 2, 1]

Referentie

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