-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

您正在寻找的概念是数字的“整数分区”。谷歌应该向你指出很多代码，或者查看我的博客以获取解释和代码。

基本思想是一个简单的递归过程。有一个0的单分区，空集()。有一个单一的分区 1，集合 (1)。有 2 的两个分区，集合 (1 1) 和 (2)。有 3 的三个分区，集合 (1 1 1)、(1 2) 和 (3)。有 4 个的五个分区，即集合 (1 1 1 1)、(1 1 2)、(1 3)、(2 2) 和 (4)。共有 5 个分区，即集合 (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 回答