Permutation Generation Function

(No, not the normal one)

I know I did this before years ago, but my mind is drawing a blank on the way I solved it.

function combos($s,$k)

A valid permutation is a combination of K integers in the range 0…S such that the sum of the integers is S.
The number of valid permutations, therefore, is vastly smaller than the replenishing permutations of s,k… but what loop structure can I create to find them all, without going through K nested loops of S length (which is highly wasteful as S increases)

why not just add them all to an array object and then array sort it?

You may also want to look at this: http://goo.gl/iqDaD

… ‘add them all’?
Add… what all?

I’m not looking for ALL permutations of the integers. Please read the post?

For example;
combos(4,5) should generate the following sets (in some order. The order isnt of concern, but the completeness is):


4,0,0,0,0
3,1,0,0,0
3,0,1,0,0
3,0,0,1,0
3,0,0,0,1
2,2,0,0,0
2,1,1,0,0
2,1,0,1,0
2,1,0,0,1
2,0,2,0,0
2,0,1,1,0
2,0,1,0,1
2,0,0,2,0
2,0,0,1,1
2,0,0,0,2
1,3,0,0,0
1,2,1,0,0
1,2,0,1,0
1,2,0,0,1
1,1,2,0,0
1,1,1,1,0
1,1,1,0,1
0,4,0,0,0
0,3,1,0,0
0,3,0,1,0
0,3,0,0,1
0,2,2,0,0
0,2,1,1,0
0,2,1,0,1
0,2,0,2,0
0,2,0,1,1
0,2,0,0,2
0,1,3,0,0
0,1,2,1,0
0,1,2,0,1
0,1,1,1,1
0,0,4,0,0
0,0,3,1,0
0,0,3,0,1
0,0,2,2,0
0,0,2,1,1
0,0,2,0,2
0,0,1,3,0
0,0,1,2,1
0,0,1,1,2
0,0,1,0,3
0,0,0,4,0
0,0,0,3,1
0,0,0,2,2
0,0,0,1,3
0,0,0,0,4

50 outputs. There is a logic pattern here, but i’m not able to extract it from my head into code.

There are 3125 permutations of 5x 0…4 - but only 50 are valid. This is why I dont want to run all possible permutations.

Well… I got there… sort of.


function recurse($sum,$pointer,$n,$k,$s) {
  if($pointer >= $k || $sum == 0) {
     if(array_sum($n) == $s) { // Why???
     return array(implode(',',$n));
	 }
	 return array();
  } else {
     $out = array();
     for($i = $sum; $i >= 0; $i--) {
	    $n[$pointer] = $i;
	    $out = array_merge($out,recurse($sum - $i,$pointer+1,$n,$k,$s));
	 }
	 return $out;
  }
}

$s = 4;
$k = 5;
$init = array_fill(0,$k,0);
$init[0] = $s;
$out = recurse($s,0,$init,$k,$s);

I’ve got a slight logic flaw in there somewhere that i’m not seeing that requires the extra IF… anybody able to spot it?