대다수의 조합 찾기

Question

N 선물을 선택할 수있는 방법의 수를 찾는 효율적인 방법은 N (N ~ 10^18) 크기 일 수 있습니다. 우리는 N (C) K 또는 N을 K를 선택해야합니다. K도 N의 순서 일 수 있습니다.

Answer 1

그런 큰 숫자를 계산하는 빠른 방법이 없다고 생각합니다. 대략적인 값은 Stirling's formula

Answer 2

입니다. C(n, k)의 값은 2^n에 가깝습니다. (음의 크기는 작지만 여기서는 중요하지 않습니다.)

숫자 2^(10^18)을 저장하는 것이 중요하다면 10^18 비트 또는 ~ 10^17 바이트가 필요합니다.
그런 컴퓨터가 없으므로 문제 정의를 조정할 수 있습니다.

다른 사람들은 결과를 부동 소수점 숫자로 저장할 수 있으므로 필요한 것보다 많은 메모리를 소비하지 않는 근사 공식을 이미 지적했습니다.

Answer 3

스털링의 공식은 k ~ n/3 또는 k ~ log n과 같은 점근 적 정보가있는 경우에만 유용합니다. 특정 문제에 대한 추가 정보가 없으면 Stirling의 수식에 대한 정보를 얻을 수 없습니다. 언급 한 바와 같이 문제를 들어

, 가장 직접적인 방법은 C를 계산하기 (N, K) 때 K 및 n은 큰 (그리고 심지어 그들이 크지 않은 경우)

log C(n, k) = log (n!) - (log (k!) + log ((n - k)!)) 

및

을 사용하는 것입니다

n! = gamma(n + 1). 

사실은 그것을 로그 감마의 구현을 제공하는 것은 매우 쉽다는 것을, 당신은 다음

C(n, k) = exp (f(n + 1) - f(k + 1) - f(n - k + 1)) 

곳이 f = log gamma.

당신은 수치 조리법, 이전 버전이 there 사용할 수 있으며 장에서 샘플 구현을 찾을 수에 컴퓨팅 로그 감마 수치 알고리즘을 찾을 수 있습니다 6. 다양한 이후

Answer 4

삶의 향신료, 또 다른 접근 방법이다 다음과 같습니다. (N 선택 K)/2^N은 평균 N/2 및 표준 편차 Sqrt [N]/2를 갖는 정규 분포에 접근하며 매우 빠르게 수행합니다. 그러므로 우리는 2^N * Normdist (x, 0,1)/std (여기서 x = (k - N/2)/std, std는 Sqrt [N]/2)로 근사합니다.
Normdist (x, 0,1) = Exp (-x^2/2) * 1/(Sqrt (2 * Pi))

오류의 관점에서 보면 이것은 더 큰 숫자 일수록 더 좋아진다. N을 113 (?)으로 사용하는 빠른 확인은 0.3 % 미만의 최대 계수의 최대 오류를 나타냅니다.

스털링 공식보다 좋다고 주장하지는 않지만, n^n 계산을 피할 수 있다고 생각하고 이러한 계수의 로그를 작성하는 것은 매우 간단한 계산입니다.