더 빠른 조합 알고리즘 작성

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

이 내가 지금까지 계승 루프를 얻을 관리했습니다 가장 빠른 :

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

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

Answer 2

IMO는 HEAVY 사용하지 않는 때문에 포인트 한계를 떠 있음을 최적화 할 가치가 없다 : (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

나는 문제가 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 

내가 Conver 유럽이 같은 실수가있는 경우 편집 주시기 바랍니다 C에서 ted 그리고 난 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; 
}