[1 BTC bounty] Recursive PHP function [CLOSED]

[payb.tc]

1 BTC going to whoever successfully translates this into a recursive function. i'm almost there but can't quite get the brain to give me the last steps.

it is a function that returns "combinations of the numbers 1 through height that add up to target, where combinations must contain exactly depth elements".

there are no duplicate combinations, and they are sorted in order from highest to lowest, eg. 3 3 1 comes before 3 2 2

Code:

$height = 6;
$depth = 4; //this is currently only represented below by the number of 'for' loops, but should feature as part of the recursive function.
$target = 21;

$results = array();

for ($a[0] = $height; $a[0] > 0; $a[0]--)
{
	for ($a[1] = $a[0]; $a[1] > 0; $a[1]--)
	{
		for ($a[2] = $a[1]; $a[2] > 0; $a[2]--)
		{
			for ($a[3] = $a[2]; $a[3] > 0; $a[3]--)
			{
				if ($a[0] + $a[1] + $a[2] + $a[3] == $target)
				{
					$results[] = array($a[0], $a[1], $a[2], $a[3]);					
				}			
			}
		}
	}
}

example ins/outs:

Code:

$height = 3;
$depth = 4;
$target = 6;

Array
(
    [0] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 1
            [3] => 1
        )

    [1] => Array
        (
            [0] => 2
            [1] => 2
            [2] => 1
            [3] => 1
        )

)


$height = 4;
$depth = 4;
$target = 12;

Array
(
    [0] => Array
        (
            [0] => 4
            [1] => 4
            [2] => 3
            [3] => 1
        )

    [1] => Array
        (
            [0] => 4
            [1] => 4
            [2] => 2
            [3] => 2
        )

    [2] => Array
        (
            [0] => 4
            [1] => 3
            [2] => 3
            [3] => 2
        )

    [3] => Array
        (
            [0] => 3
            [1] => 3
            [2] => 3
            [3] => 3
        )

)

i'll see how this goes, and see if i can work it out myself too, or maybe up the bounty later if it drags out.

cheers.

p.s. unfortunately all attempts to search for combination-calculating code on the web actually return mis-named results for permutations instead.

[payb.tc]

closed... figured it out:

Code:

docalc($height, $depth, $target);

function docalc($height, $depth, $target, $arr = array())
{
	if (count($arr) == $depth)
	{
		$total = 0;
		
		foreach ($arr as $element)
		{
			$total += $element;
		}
		
		if ($total == $target)
		{
			echo implode(' ', $arr) . '<br/>';
		}
	}
	else
	{
		for ($a = $height; $a > 0; $a--)
		{
			docalc($a, $depth, $target, array_merge($arr, array($a)));
		}
	}
	
}

[mintymark]

Shame its closed, but I'll post my solution in any case.

<?php

$a = array();

$h=4;
$d=4;
$t=12;

level($h,$d,$t);
exit;

function level($h,$d,$t)
{
   global $a;

  if ($d==0 and $t==0) printout();

  if ($d==0) return;
  if ($t<$d) return;

   while ($h>0)
   {
     array_push($a,$h);
     level($h,$d-1,$t-$h);
     array_pop($a);
     $h--;
   }
}

function printout()
{
   global $a;
   $c=0;
   # print "**: ";
   while ($c < sizeof($a))
   {
      printf("%d ", $a[$c]);
      $c++;
   }
   print "\n";
}
?>

[mintymark]

So is there a consolation prize?