-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のパーティションがある場合、パーティション内の最小の項目から1を引くことにより、標準的な方法でn-1のパーティションに減らすことができます。例：1 + 2 + 3 => 2 + 3、2 + 4 => 1+4。このアルゴリズムはプロセスを逆にします。n-1のパーティションpごとに、このプロセスによってpに削減されるnのパーティションを見つけます。したがって、nの各パーティションは、それが減少するn-1のパーティションが考慮されるステップで、1回だけ出力されます。

これは、Pythonで数値の可能なすべてのパーティションを取得するためのコードです。私はPythonが苦手です。誰かがそれを擬似コード（または詳細な説明）またはPHPに変換していただければ幸いです。上記の説明は、「パーティション内の最小のアイテムから1つを差し引く」ことについての私の心に疑問を投げかけます。2番目に小さい要素または他の要素から1を引くこともできます。では、なぜ最小なのか？誰かが私に全体の考えを説明することができれば、それは本当にありがたいです。ありがとう。

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

これが私の試みです（私の知る限り、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 に答える