Für Permutationen mit N und k habe ich eine Funktion, die die k th Permutation von N in lexikographischer Reihenfolge findet. Auch bei einer Permutation perm habe ich eine Funktion, die den lexikographischen Index der Permutation unter allen Permutationen von N findet. Um dies zu tun, habe ich die "faktorielle Zerlegung" wie in diese Antwort vorgeschlagen.
Nun möchte ich dasselbe für ganzzahlige Partitionen von N machen. Für N=7 möchte ich beispielsweise zwischen dem Index (links) und der Partition (rechts) hin- und herspringen können:
Ich habe ein paar Dinge ausprobiert. Das Beste, was mir einfiel, war
%Vor%was folgendes ergibt:
%Vor% Das funktioniert nicht ganz, scheint aber auf dem richtigen Weg zu sein. Ich habe mir das ausgedacht, weil es zählt, wie oft ich eine Zahl nach unten bewegen muss (wie 6,3,2 zu 6,3,1,1 geht). Ich kann jedoch nicht sehen, wie ich es beheben kann, weil ich nicht weiß, wie man Rechenschaft ablegen muss, wenn Dinge neu kombiniert werden müssen (wie 6,3,1,1 geht zu 6,2,2 ).
Denken Sie darüber nach, warum die "faktorielle Zerlegung" für Permutationen funktioniert, und die gleiche Logik funktioniert hier. Anstatt jedoch k! für die Anzahl der Permutationen von k -Objekten zu verwenden, müssen Sie die Partitionsfunktion p(n,k) für die Anzahl der Partitionen von n mit dem größten Teil höchstens k verwenden. Für n=7 sind diese Zahlen:
Um den lexikographischen Index von (3,2,1,1) zu erhalten, berechnen Sie beispielsweise
was 15 - [4 + 1 + 0 + 0] - 1 = 9 ist. Hier berechnen Sie die Anzahl der Partitionen von 7 mit dem größten Teil weniger als 3 plus die Anzahl der Partitionen von 4 mit dem größten Teil weniger als 2 plus ... Die gleiche Logik kann dies umkehren. In C sind die (nicht getesteten!) Funktionen:
Hier sollte numPar(int n) die Anzahl der Partitionen von n zurückgeben, und numPar(int n, int k) sollte die Anzahl der Partitionen von n mit dem größten Teil höchstens k zurückgeben. Sie können diese selbst unter Verwendung von Wiederholungsrelationen schreiben.
Tags und Links algorithm c lexicographic integer-partition