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

Question

Я пытаюсь написать комбинаторный алгоритм, чтобы получить все возможные комбинации 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);
}

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

Answer 1

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

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

Также для эффективности1006 * Не стесняйтесь редактировать, если есть ошибка, поскольку я преобразовал ее из 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;
}

Answer 2

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

Answer 3

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

Answer 4

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

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);
}

Answer 5

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

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

    $factorial = 1;
    while ($factVal > 1) {
        $factorial *= $factVal--;
    }
    return $factorial ;
}