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

Я пытаюсь написать комбинаторический алгоритм, чтобы получить все возможные комбинации k из n без повторений.

Формула такова: 

n!/(k!(n-k)!));

Результаты в конечном итоге попадают в массив. На самом деле я написал вот что:

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

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

    return($ans);
}

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

    return ($ans);
}

Это самый быстрый способ добиться этого? Есть ли способ ускорить это? Может быть, написать его рекурсивно?

Author: templatetypedef, 2011-12-28
Source

5 answers

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

function Factorial($factVal) {
    if ($factVal < 0) {
        die("Factorial() Error: Number too small!");
    }

    $factorial = 1;
    while ($factVal > 1) {
        $factorial *= $factVal--;
    }
    return $factorial ;
}
 1
Author: Mark Baker, 2011-12-27 23:50:38

Я думаю, что проблема в том, чтобы вычислить 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,n-k), therefore choose which ever is smaller k or n-k

Не стесняйтесь редактировать, если есть ошибка, так как я преобразовал ее из 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;
}
 6
Author: FUD, 2011-12-28 04:52:19

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

 2
Author: Andrzej Bort, 2011-12-27 23:54:13 
function Factorial($x)
{
    if ($x < 1)
    {
        echo "Factorial() Error: Number too small!";
    }

Это неправильно, 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! и, таким образом, дают точные результаты для более широкий диапазон чисел.

 2
Author: Daniel Fischer, 2011-12-28 00:42:39

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

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

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

Вот черновик этого подхода: 

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);
}
 1
Author: Ted Hopp, 2011-12-28 02:12:59