Topic: [1 BTC bounty] Recursive PHP function [CLOSED] (Read 653 times)
So is there a consolation prize?
Shame its closed, but I'll post my solution in any case.
$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";
}
?>
$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";
}
?>
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) . '
';
}
}
else
{
for ($a = $height; $a > 0; $a--)
{
docalc($a, $depth, $target, array_merge($arr, array($a)));
}
}
}
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) . '
';
}
}
else
{
for ($a = $height; $a > 0; $a--)
{
docalc($a, $depth, $target, array_merge($arr, array($a)));
}
}
}
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
example ins/outs:
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.
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]);
}
}
}
}
}
$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
)
)
$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.
Jump to: