El coeficiente binomial es una función muy utilizada en combinatoria. Sirve para saber el número de combinaciones de elementos que podemos hacer. Se utiliza mucho en computación para estudiar la estrategia de programación dinámica, porque ejemplifica muy bien la mejora que supone utilizar dicha estrategia. Por ejemplo, la forma de escoger de entre 6 elementos 2 de ellos, es igual al coeficiente binomial (6 2).
Su definición es:
Binomial(n, k) = 1, si k=0 o k=n
Binomial(n, k) = Binomial(n-1, k-1) + Binomial(n-1, k), en otro casi
Partiendo de esta definición tenemos en PHP el siguiente código:
function binomialRecursive($n, $k)
{
if ($k == 0 or $k == $n) {
return 1;
} else {
return binomialRecursive($n - 1, $k - 1) + binomialRecursive($n - 1, $k);
}
}
Para números grandes se repiten cálculos muchas veces, con lo que reducimos su coste temporal aplicando programación dinámica:
function binomialDynamic($n, $k)
{
$tablaNK = array();
if ($k <= 0 or $k == $n) {
return 1;
} else {
for ($i = 0; $i <= $n; ++$i) {
$tablaNK[$i][0] = 1;
}
for ($i = 1; $i <= $k; ++$i) {
$tablaNK[$i][$i] = 1;
}
for ($i = 2; $i <= $n; ++$i) {
for ($j = 1; $j < $i; ++$j) {
if ($j <= $k) {
$tablaNK[$i][$j] = $tablaNK[$i - 1][$j - 1] + $tablaNK[$i - 1][$j];
}
}
}
/*for ($i = 0; $i < $n; ++$i) {
for ($j = 0; $j < $k; ++$j) {
if ($j <= $i) {
echo str_pad($tablaNK[$i][$j], 3);
}
}
echo PHP_EOL;
}*/
return $tablaNK[$n][$k];
}
}
Entonces iremos recorriendo de izquierda a derecha y de arriba a abajo rellenando la tabla. No tendremos que recalcular de nuevo ningún binomial anterior, con lo que el coste temporal final va a ser lineal.
Igual que en el post anterior, si metemos las dos funciones recursiva y dinámica en un bucle podemos ver cómo evolucionan. El código fuente en PHP queda así:
define('MAX_N', 100);
for ($n = 3; $n <= MAX_N; ++$n) {
$k = intval($n / 2);
$timeStart = microtime(true);
$theNumber = binomialRecursive($n, $k);
//echo 'binomialRecursive('.$n.', '.$k.') = '.$theNumber.PHP_EOL;
$timeEnd = microtime(true);
echo 'RECURSIVE binomial('.$n.','.$k.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;
$timeStart = microtime(true);
$theNumber = binomialDynamic($n, $k);
//echo 'binomialDynamic('.$n.', '.$k.') = '.$theNumber.PHP_EOL;
$timeEnd = microtime(true);
echo ' DYNAMIC binomial('.$n.','.$k.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;
}
Ponemos todo en un fichero y al ejecutarlo podremos ver claramente que tenemos que usar programación dinámica. Para números grandes, no podremos calcular sus binomiales si no es aplicando programación dinámica.
RECURSIVE binomial(6,3): Calculated in 0.000006914 seconds. DYNAMIC binomial(6,3): Calculated in 0.000010014 seconds. RECURSIVE binomial(7,3): Calculated in 0.000009060 seconds. DYNAMIC binomial(7,3): Calculated in 0.000010014 seconds. RECURSIVE binomial(8,4): Calculated in 0.000020981 seconds. DYNAMIC binomial(8,4): Calculated in 0.000010014 seconds. RECURSIVE binomial(9,4): Calculated in 0.000045061 seconds. DYNAMIC binomial(9,4): Calculated in 0.000010014 seconds. RECURSIVE binomial(10,5): Calculated in 0.000081062 seconds. DYNAMIC binomial(10,5): Calculated in 0.000010967 seconds. RECURSIVE binomial(11,5): Calculated in 0.000133038 seconds. DYNAMIC binomial(11,5): Calculated in 0.000012159 seconds. RECURSIVE binomial(12,6): Calculated in 0.000247002 seconds. DYNAMIC binomial(12,6): Calculated in 0.000014067 seconds. RECURSIVE binomial(13,6): Calculated in 0.000452042 seconds. DYNAMIC binomial(13,6): Calculated in 0.000015974 seconds. RECURSIVE binomial(14,7): Calculated in 0.000910997 seconds. DYNAMIC binomial(14,7): Calculated in 0.000026941 seconds. RECURSIVE binomial(15,7): Calculated in 0.001642227 seconds. DYNAMIC binomial(15,7): Calculated in 0.000020027 seconds. RECURSIVE binomial(16,8): Calculated in 0.003252029 seconds. DYNAMIC binomial(16,8): Calculated in 0.000024080 seconds. RECURSIVE binomial(17,8): Calculated in 0.005996943 seconds. DYNAMIC binomial(17,8): Calculated in 0.000023842 seconds. RECURSIVE binomial(18,9): Calculated in 0.013009787 seconds. DYNAMIC binomial(18,9): Calculated in 0.000043154 seconds. RECURSIVE binomial(19,9): Calculated in 0.020354033 seconds. DYNAMIC binomial(19,9): Calculated in 0.000036001 seconds. RECURSIVE binomial(20,10): Calculated in 0.036875963 seconds. DYNAMIC binomial(20,10): Calculated in 0.000036955 seconds. RECURSIVE binomial(21,10): Calculated in 0.061520815 seconds. DYNAMIC binomial(21,10): Calculated in 0.000036955 seconds. RECURSIVE binomial(22,11): Calculated in 0.120537996 seconds. DYNAMIC binomial(22,11): Calculated in 0.000041008 seconds. RECURSIVE binomial(23,11): Calculated in 0.230448008 seconds. DYNAMIC binomial(23,11): Calculated in 0.000044107 seconds. RECURSIVE binomial(24,12): Calculated in 0.459716797 seconds. DYNAMIC binomial(24,12): Calculated in 0.000044823 seconds. RECURSIVE binomial(25,12): Calculated in 0.885799885 seconds. DYNAMIC binomial(25,12): Calculated in 0.000042915 seconds. RECURSIVE binomial(26,13): Calculated in 1.761939049 seconds. DYNAMIC binomial(26,13): Calculated in 0.000046015 seconds. RECURSIVE binomial(27,13): Calculated in 3.628232956 seconds. DYNAMIC binomial(27,13): Calculated in 0.000091076 seconds. RECURSIVE binomial(28,14): Calculated in 7.495334148 seconds. DYNAMIC binomial(28,14): Calculated in 0.000072956 seconds. RECURSIVE binomial(29,14): Calculated in 13.519285917 seconds. DYNAMIC binomial(29,14): Calculated in 0.000084877 seconds. RECURSIVE binomial(30,15): Calculated in 27.332123995 seconds. DYNAMIC binomial(30,15): Calculated in 0.000058174 seconds. RECURSIVE binomial(31,15): Calculated in 53.179553986 seconds. DYNAMIC binomial(31,15): Calculated in 0.000060081 seconds. RECURSIVE binomial(32,16): Calculated in 107.939800024 seconds. DYNAMIC binomial(32,16): Calculated in 0.000065088 seconds. RECURSIVE binomial(33,16): Calculated in 203.573032141 seconds. DYNAMIC binomial(33,16): Calculated in 0.000068903 seconds. RECURSIVE binomial(34,17): Calculated in 409.646430969 seconds. DYNAMIC binomial(34,17): Calculated in 0.000072002 seconds.
