Algorithmus Übersetzung PHP oder Pseudo-Code von Python für Partition einer ganzen Zahl

Question

def partitions(n): 
    # base case of recursion: zero is the sum of the empty list 
    if n == 0: 
     yield [] 
     return 

    # modify partitions of n-1 to form partitions of n 
    for p in partitions(n-1): 
     yield [1] + p 
     if p and (len(p) < 2 or p[1] > p[0]): 
      yield [p[0] + 1] + p[1:] 

Erläuterung: Wenn Sie eine Partition von n haben, können Sie es auf eine Partition von n-1 in kanonischer Weise reduzieren, indem man aus der Subtraktion kleinstes Element in der Partition. Z.B. 1 + 2 + 3 => 2 + 3, 2 + 4 => 1 + 4. Dieser Algorithmus kehrt den Prozess um: Er findet für jede Partition p von n-1 die Partitionen von n, die durch diesen Prozess auf p reduziert werden. Daher wird jede Partition von n in dem Schritt genau einmal ausgegeben, wenn die Partition von n-1, auf die sie reduziert wird, betrachtet wird.

Dies ist ein Code zum Abrufen aller möglichen Partitionen einer Zahl in Python. Ich bin nicht gut in Python. Ich würde es sehr schätzen, wenn jemand es einfach in Pseudocode (oder detaillierte Beschreibung) oder in PHP transformieren könnte. Die obige Erklärung erzeugt einen Zweifel darüber, "einen von dem kleinsten Gegenstand in der Partition zu subtrahieren". Ich kann auch eins vom zweitkleinsten oder einem anderen Element subtrahieren. Also, warum nur am kleinsten? Wenn mir jemand die ganze Idee erklären könnte, wäre es wirklich dankbar. Danke.

Answer 1

def partitions(n): 
    # base case of recursion: zero is the sum of the empty list 
    if n == 0: 
     yield [] # yield empty array 
     return # exit function 

    # modify partitions of n-1 to form partitions of n 
    for p in partitions(n-1): # recursive call, get n-1 partitions 
     yield [1] + p # yield array [1, p...] 
     if p and (len(p) < 2 or p[1] > p[0]): # p not empty, and length < 2 or p[1] > p[0] 
      yield [p[0] + 1] + p[1:] # increment first item of p and yield p 

Hier ist mein Versuch (afaik PHP nicht yield hat, so könnte es schlimmer ausführen):

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

    # modify partitions of n-1 to form partitions of n 
    $a = array(); # will hold "yielded" values 
    foreach(partitions($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 
} 

(Ich garantiere nichts)