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

说明：如果您有一个 n 的分区，您可以通过从分区中的最小项目中减去一个以规范的方式将其减少为 n-1 的分区。例如 1+2+3 => 2+3、2+4 => 1+4。该算法反转该过程：对于 n-1 的每个分区 p，它找到 n 的分区，该分区将通过此过程减少为 p。因此，n 的每个分区恰好输出一次，在考虑它减少到的 n-1 分区的步骤中。

这是用于在 Python 中获取数字的所有可能分区的代码。我不擅长 Python。如果有人可以将其转换为伪代码（或详细描述）或 PHP，我将不胜感激。上面的解释让我对“从分区中最小的项目中减去一个”产生了疑问。我也可以从第二小的元素或其他元素中减去一个。那么，为什么只有最小的呢？如果有人可以向我解释整个想法，那将非常感激。谢谢。

4

1 回答 1

2 
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

这是我的尝试（afaik PHP 没有yield，因此它的性能可能会更差）：

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
}

（我不保证什么）

于 2012-04-06T09:42:57.670 回答