Напишите алгоритм более быстрой комбинаторики

Это самый быстрый, который мне когда-либо удалось получить факториальную петлю:

 function Factorial($factVal) { if ($factVal < 0) { die("Factorial() Error: Number too small!"); } $factorial = 1; while ($factVal > 1) { $factorial *= $factVal--; } return $factorial ; } 

Я думаю, что проблема состоит в том, чтобы вычислить C (n, k), который можно сделать без вычисления факториала, трюк должен отметить сначала, что

 C(n,k) = (n*(n-1)...(n-k+1)) / (1*2*...*k) = (n/1)*(n-1/2)*...(n-k+1/k) 

Также для эффективности

 C(n,k) = C(n,nk), therefore choose which ever is smaller k or nk 

Не стесняйтесь редактировать, если есть ошибка, поскольку я преобразовал ее из C и я не знаю php

 function nCk($n, $k) { if( $n-$k<$k ) $k = $n-$k; $ans = 1; for( $i=1; $i<=$k; ++$i ) { $ans = ($ans*($n-$i+1))/$i; } return $ans; } 

ИМО не стоит оптимизировать это, если не использовать ТЯЖЕЛЫЕ из-за ограничений по плавающей точке: 170! = 7.257415615308E + 306, а следующий факториал (171!) Выходит за пределы диапазона с плавающей запятой. Я предполагаю, что рекурсия будет замедлять процесс (но не проверять его).

 function Factorial($x) { if ($x < 1) { echo "Factorial() Error: Number too small!"; } 

Это неправильно, 0! = 1 0! = 1 , поэтому тест должен быть равен $x < 0 .

  $ans = 1; for ($xx = 2; $xx >= $x; $xx++) 

Вы опечатали условие, оно должно быть $xx <= $x .

 function Combination($selectcount,$availablecount) { $ans = Factorial($availablecount) / ( Factorial($availablecount - $selectcount) * Factorial($selectcount) ); return ($ans); } 

У вас есть две потенциальные проблемы,

1. вызов Factorial функции происходит медленнее, чем цикл, вычисляющий счет комбинации здесь
2. факториалы становятся очень большими, поэтому вы рискуете переполнением и неточностями, где вам не нужно

Являются ли эти фактические проблемы, зависит от вашего приложения. Вы написали, что результаты попадают в массив, по-видимому, чтобы избежать перерасчета, поэтому скорость для начального расчета менее важна. Однако проблемы с переполнением вполне могут быть. Чтобы избежать этого, вычислите рекурсивные записи массива на треугольник Паскаля, choose(n+1,k) = choose(n,k) + choose(n,k-1) , где choose(n,k) = 0 если k < 0 или k > n . В качестве альтернативы вы можете рассчитать каждую строку, начиная с choose(n,0) = 1 и choose(n,k) = choose(n,k-1)*(n+1-k)/k для 1 <= k <= n . Оба метода избегают большого промежуточного n! и, таким образом, дают точные результаты для более широкого диапазона чисел.

Вам действительно не нужно вычислять полный числитель и знаменатель. Например:

 C(7,2) = 7! / (2! * (7-2)!) = 7! / (2! * 5!) = (7 * 6) / (2 * 1) 

То есть наибольший фактор знаменателя отменяет самую низкую часть факториала числителя. Так, например, если k> n / 2, все, что вам нужно сделать, это умножить числа от k + 1 на n и затем делить на (nk) !. Это экономит значительную работу по вычислению полного факториала.

Вот пример этого подхода:

 function Combination($selectcount,$availablecount) { $remainder = $availablecount - $selectcount; if ($remainder > $selectcount) { $tmp = $remainder; $remainder = $selectcount; $selectcount = $tmp; } $ans = 1; while ($availablecount > $selectcount) { $ans *= $availablecount; $availablecount--; } while ($remainder > 1) { $ans /= $remainder; $remainder--; } return ($ans); }