нахождение комбинаторных больших чисел

Question

Что является эффективным способом определения количества способов, которыми k подарков можно выбрать из N подарков, где N может быть очень большим (N ~ 10 ^ 18). То есть мы должны рассчитать N (C) K или N, выбрав K. K также может иметь порядок N.

Answer 1

Я думаю, что нет быстрых способов вычислить такие большие числа.Вы можете приблизить его, используя формула Стирлинга

Answer 2

Поскольку разнообразие - это специя жизни, другой подход заключается в следующем. Значение (N Выберите K) / 2 ^ N приближается к нормальному распределению со средним N / 2 и стандартным отклонением Sqrt [N] / 2, и это происходит довольно быстро. Поэтому мы можем приблизить (N Выберите K) как 2 ^ N * Normdist (x, 0,1) / std, где x = (k - N / 2) / std и std, это Sqrt [N] /2.
Нормдист (x, 0,1) = Exp (-x ^ 2/2) * 1 / (Sqrt (2 * Pi))

С точки зрения ошибки, чем больше число, тем лучше, и быстрая проверка с использованием N как 113 (?) Показывает максимальную ошибку как процент от наибольшего коэффициента менее 0,3%.

Не утверждая, что это лучше, чем использование формулы Стирлинга, но подумайте, что это может избежать некоторых из n ^ n вычислений, и вычислить логарифм этих коэффициентов довольно просто.

Answer 3

Формула Стирлинга будет полезна, только если у вас будет дополнительная асимптотическая информация, такая как k ~ n / 3 или k ~ log n.Не имея дополнительной информации о вашей конкретной проблеме, вы не будете черпать информацию о формуле Стирлинга.

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

Вы можете найти численные алгоритмы для вычисления гаммы журнала в Числовые рецепты , старая версия доступна там , и вы найдете пример реализации в главе 6.

Answer 4

Значение C(n, k) может быть близко к 2^n.(ну, на порядок меньше, но здесь это не важно).

Что важно для хранения числа 2^(10^18), вам нужно 10^18 бит или ~ 10^17 байт.
Возможно, вы захотите настроить определение проблемы, потому что таких компьютеров нет.

Другие уже указали приблизительную формулу, где вы можете сохранить результат в виде числа с плавающей запятой, таким образом, не тратя больше памяти, чем необходимо.