-1

たとえば、3 を入力すると、[1,1,1]、[2,1]、および [1,2] が返されます。

多くの組み合わせ/順列の問題には、ループ内で自分自身を呼び出す再帰関数が含まれていることは知っていますが、それをこの問題に適用する適切な方法がわかりません。

それは私が把握しようとしている概念です。これが私がこれまでに持っているものです...

function numberToAddends($number, $arr, $k){
    for ($i = 0; $i < $number; $i++) {
        $arr[$k] = $i;
        numberToAddends($k-$i, $arr, $k + 1);
    }

    if($k <=0){
        print_r($arr);
    }
}

テスト入力には、numberToAddends(3, $arr, 0); のようなものを使用できます。

私は正しい道に沿って考えていますか？コメント付きのコードとともに、この問題を解決するための完全な php 構文を提供できる人はいますか?

4

2 に答える 2

2

あなたが探している概念は、数値の「整数パーティション」です。Google は、多くのコードを示しているはずです。または、説明とコードについては私のブログを参照してください。

基本的な考え方は単純な再帰プロセスです。0 の単一のパーティション、空のセット () があります。1、セット (1) の単一のパーティションがあります。2 の 2 つのパーティション、セット (1 1) と (2) があります。3 の 3 つのパーティション、セット (1 1 1)、(1 2)、および (3) があります。セット (1 1 1 1)、(1 1 2)、(1 3)、(2 2)、および (4) の 4 の 5 つのパーティションがあります。5 の 7 つのパーティション、セット (1 1 1 1 1)、(1 1 1 2)、(1 2 2)、(1 1 3)、(1 4)、(2 3)、および (5) があります。等々。いずれの場合も、n − x の分割によって形成されるすべてのセットに、目的の整数 n 以下の各整数 x を追加し、重複を排除することによって、次に大きな分割のセットが決定されます。

于 2013-01-23T20:04:34.140 に答える
1

1 からnまでのサブ結果を再利用することで、この問題を解決するアルゴリズムを次に示します。

$number = 3;
$addends = array();
for ($x=1; $x<=$number; $x++) {
    $addends[$x] = array();
    for ($y=$x-1; $y>0; $y--) {
        foreach ($addends[$y] as $z) {
            $addends[$x][] = array_merge($z, array($x-$y));
        }
    }
    $addends[$x][] = array($x);
}
var_dump($addends);

これは、任意のy < xの既知の結果zをxとyの差、そして最後にx自体と組み合わせることにより、 xの結果セットを構築します。

于 2013-01-23T20:04:45.957 に答える