effiziente Möglichkeit, ungleiche Partitionen einer ganzen Zahl zu finden

Question

Ich habe insgesamt Partitionen einer ganzen Zahl und ich will nur diejenigen Partitionen, die alle Werte ungleich haben. Für ex.-Partitionen von 3 sind {1,1,1,1}, {2,2}, {3,1}, {1,1,2} und {4}. Daher sind die erforderlichen ungleichen Partitionen {3,1} und {4}, weil sie keine gleichen Elemente enthalten. Der Code, den ich für das Auffinden aller Partitionen verwendet habe, ist unten aufgeführt. Ich kann die Partitionen filtern, um das gewünschte Ergebnis zu erhalten, aber ich möchte einen effizienten Weg finden, alle Partitionen zu finden, die keine gleichen Bedingungen haben, ohne alle Partitionen zu finden. Ich habe das Netz und Stackoverflow durchsucht, aber nichts sagt genau das Problem aus, dem ich gegenüberstehe. Jede Idee wird geschätzt. Vielen Dank.

function total_partitions_of_a_number($n) {# base case of recursion: zero is the sum of the empty list 
if(!$n) return array(array()); # return empty array 

# modify partitions of n-1 to form partitions of n 
foreach(total_partitions_of_a_number($n-1) as $p) { # recursive call 
$a[] = array_merge(array(1), $p); # "yield" array [1, p...] 
if($p && (count($p) < 2 || $p[1] > $p[0])) { # p not empty, and length < 2 or p[1] > p[0] 
    ++$p[0]; # increment first item of p 
    $a[] = $p; # "yield" p 
} 
} 
return $a; # return all "yielded" values at once 
} 

Answer 1

Sie wollen nur Partitionen, wo eine bestimmte Komponente nicht mehr als einmal erscheint? Die Rekursion ist einfach.

Reduzieren Sie es auf das Problem der Lösung für die Partitionen von N, so dass kein Element in der Menge größer als ein Wert ist (a wird zunächst N sein.) Nun, ein entweder tut oder nicht in der Partition . Abhängig davon werden Sie beide rekursiv auf die Partitionen von (N-a) auflösen, so dass kein Element größer als a-1 ist, und für die Partitionen von N so, dass kein Element größer als a-1 ist.

In jedem Fall ist die Rekursion gut gestellt und wird beendet, wenn es nicht mehr möglich ist, das Problem zu lösen, also wenn ein * (a + 1)/2 < N. Natürlich, wenn a * (a + 1)/2 = N, können Sie die Rekursion auch schnell beenden, da die Lösung dann eindeutig ist.