algorithm translation to php or pseudocode from python for partition of an integer [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

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:]

Explanation: If you have a partition of n, you can reduce it to a partition of n-1 in a canonical way by subtracting one from the smallest item in the partition. E.g. 1+2+3 => 2+3, 2+4 => 1+4. This algorithm reverses the process: for each partition p of n-1, it finds the partitions of n that would be reduced to p by this process. Therefore, each partition of n is output exactly once, at the step when the partition of n-1 to which it reduces is considered.

This is code for getting all possible partitions of a number in Python. I am not good at Python. I would really appreciate if someone could just get it transformed into pseudocode(or detailed description) or in PHP. The explanation above creates a doubt in my mind about "subtracting one from the smallest item in the partition". I can also subtract one from second smallest or some other element. So, why only smallest? If someone could explain me the whole idea, it would be really grateful. Thanks.

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

Here's my try (afaik PHP does not have yield, so it might perform worse):

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
}

(I don't guarantee anything)