如何返回給定整數給定正整數的所有數字序列？

-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語法來解決這個問題以及評論代碼嗎？

來源

2013-01-23 user784637

它不應該給'[3]'作爲解決方案嗎？ – phimuemue

*評論代碼*，一些咖啡，或許是一個很好的甜甜圈？ – 2013-01-23 19:53:15

不，原來的號碼都是 – user784637

下面是通過重用子結果從1至ň解決這個問題的算法：

$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);

這將構建組合的任何已知結果ž爲X設置結果任何ÿ < X與X和y中的差最後x本身。

來源

2013-01-23 20:04:45 Gumbo

您正在尋找的概念是一個數字的「整數分區」。谷歌應該爲您提供很多代碼，或者查看my blog獲取解釋和代碼。

基本思想是一個簡單的遞歸過程。有一個單獨的分區0，空的set（）。有一個單獨的分區1，集合（1）。有兩個分區2，集合（1 1）和（2）。有三個分區3，集合（1 1 1），（1 2）和（3）。有5個分區，分別爲（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-23 20:04:34 user448810

如何返回給定整數給定正整數的所有數字序列？

回答

相關問題