이 알고리즘을 가장 컴팩트 한 방식으로 대규모 조합에 대해 어떻게 작성 하시겠습니까?

StackOverflow https://stackoverflow.com/questions/956542

문제

조합의 수 k 검색 할 수있는 항목 N 항목은 다음 공식으로 설명됩니다.

             N! 
c =  ___________________ 
       (k! * (N - k)!)

예를 들어 얼마나 많은 조합이 있습니다 6 Balls 드럼에서 그릴 수 있습니다 48 Balls 복권 추첨에서.

가장 작은 O 시간 복잡성으로 실행되도록이 공식을 최적화하십시오.

이 질문은 새로운 Wolframalpha 수학 엔진에서 영감을 얻었으며 매우 큰 조합을 매우 빠르게 계산할 수 있다는 사실에서 영감을 얻었습니다. 예를 들어 다른 포럼의 주제에 대한 후속 토론.

http://www97.wolframalpha.com/input/?i=20000000+ Choose+15000000

일부 사람들이 솔루션을 찌르고 나서 그 토론에서 정보/링크를 게시하겠습니다.

모든 언어는 허용됩니다.

도움이 되었습니까?

해결책

Wolframalpha는 "소수점 근사치"를 반환합니다. 절대적 정밀도가 필요하지 않으면 팩토리 노트를 계산하여 같은 일을 할 수 있습니다. 스털링의 근사.

이제 스털링의 근사치에는 (n/e)^n의 평가가 필요하며, 여기서 e는 자연 로그의 기초인데, 이는 가장 느린 작업이 될 것입니다. 그러나 이것은 요약 된 기술을 사용하여 수행 할 수 있습니다. 또 다른 stackoverflow 게시물.

지수를 달성하기 위해 이중 정밀도와 반복 사각형을 사용하는 경우 작업은 다음과 같습니다.

  • 3 스털링 근사치 평가, 각각 O (log n) 곱셈 및 1 개의 제곱근 평가가 필요합니다.
  • 2 개의 곱셈
  • 1 부서

약간의 영리함으로 운영의 수를 줄일 수 있지만,이 접근법에서는 총 시간 복잡성이 O (log n)가 될 것입니다. 꽤 관리 가능합니다.

편집 :이 계산이 얼마나 흔한지를 감안할 때이 주제에 대한 많은 학문적 문헌이 있어야합니다. 좋은 대학 도서관은 당신이 그것을 추적하는 데 도움이 될 수 있습니다.

EDIT2 : 또한 다른 응답에서 지적한 바와 같이, 값은 2 배를 쉽게 넘어 낼 것이므로, 정밀도가 매우 확장 된 부동 소수점 유형은 k와 n의 값에 있어도 적당히 큰 값에 사용해야합니다.

다른 팁

파이썬 : 영형(최소 [케이,N-케이]2)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

분석:

  • 의 크기 p 그리고 q 루프 내부에서 선형으로 증가합니다 n-i 그리고 1+i 일정한 크기를 갖는 것으로 간주 될 수 있습니다.
  • 각 곱셈의 비용도 선형으로 증가합니다.
  • 이 모든 반복의 합계는 산술 시리즈가됩니다. k.

내 결론 : 영형(k2)

플로팅 포인트 번호를 사용하도록 다시 작성하면 곱셈은 원자 연산이지만 많은 정밀도를 잃게됩니다. 심지어 오버플로됩니다 choose(20000000, 15000000). (결과는 약 0.2119620413 × 10이기 때문에 큰 놀라움은 아닙니다.4884378.)

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

나는 그것을 해결할 것이다 수학:

Binomial[n, k]

남자, 그것은 쉬웠다 ...

파이썬 : 근사 영형(1) ?

Python Decimal 구현을 사용하여 근사치를 계산합니다. 외부 루프를 사용하지 않고 숫자의 크기가 제한되어 있으므로 영형(1).

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

예시:

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

더 높으면 오버플로됩니다. 지수는 40000000으로 제한 된 것 같습니다.

N 및 K에 대한 합리적인 수의 값이 주어지면 미리 계산하고 조회 테이블을 사용하십시오.

그것은 어떤 방식으로 문제를 피하고 있습니다 (계산을 오프로드하고 있음). 그러나 많은 값을 결정 해야하는 경우 유용한 기술입니다.

Matlab :

  • 사기꾼의 방식 (내장 기능 사용 Nchoosek): 13 자, o (?)

    nchoosek(N,k)

  • 내 해결책 : 36 자, O (Min (K, NK))

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)

나는 이것이 정말 오래된 질문이라는 것을 알고 있지만 VB 6에 작성된 정말 간단한 것을 발견하고 C#로 포팅 한 후에는 다음과 같은 결과가 있습니다.

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

최종 코드는 너무 간단하여 실행할 때까지 작동하지 않을 것이라고 믿지 않을 것입니다.

또한, 원본 기사 그가 최종 알고리즘에 어떻게 도달했는지에 대한 좋은 설명을 제공합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top