Как бы вы написали этот алгоритм для больших комбинаций наиболее компактным способом?

Question

Количество комбинаций k элементов, которые можно извлечь из N элементов, описывается следующей формулой.

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

Примером может служить количество комбинаций 6 Balls, которые можно извлечь из барабана 48 Balls в лотерее.

Оптимизируйте эту формулу для запуска с наименьшей трудоемкостью O

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

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

Я опубликую некоторую информацию / ссылки из этого обсуждения после того, как некоторые люди попробуют решение.

Допустим любой язык.

Answer 1

Python: O (мин [ k , n - k ] ² )

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.

Мой вывод: O (k ² )

Если переписать для использования чисел с плавающей запятой, умножения будут атомарными операциями, но мы потеряем большую точность. Это даже переполняется для 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

Answer 2

Обратите внимание, что WolframAlpha возвращает "Десятичное приближение". Если вам не нужна абсолютная точность, вы можете сделать то же самое, вычислив факториалы с приближением Стирлинга .

Теперь, приближение Стирлинга требует оценки (n / e) ^ n, где e - основание натурального логарифма, который будет безусловно самой медленной операцией. Но это можно сделать, используя методы, описанные в другой публикации stackoverflow .

Если вы используете двойную точность и повторное возведение в квадрат для выполнения возведения в степень, операции будут:

• 3 оценки приближения Стирлинга, каждая из которых требует O (log n) умножений и одного квадратного корня.
• 2 умножения
• 1 деление

Количество операций, вероятно, можно было бы уменьшить с некоторой сообразительностью, но общая сложность времени при этом подходе составит O (log n). Довольно управляемый.

РЕДАКТИРОВАТЬ: Там также обязательно будет много научной литературы по этой теме, учитывая, насколько распространены эти расчеты. Хорошая университетская библиотека может помочь вам отследить ее.

EDIT2: Кроме того, как указано в другом ответе, значения легко переполняются двойным, поэтому тип с плавающей запятой с очень высокой точностью потребуется использовать даже для умеренно больших значений k и n.

Answer 3

Python: приближение в O (1)?

Использование десятичной реализации python для вычисления аппроксимации. Поскольку он не использует какой-либо внешний цикл, а числа ограничены в размере, я думаю, что он будет выполняться в O (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.

Answer 4

Я бы решил это в Mathematica :

Binomial[n, k]

Чувак, это было легко ...

Answer 5

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

Окончательный код настолько прост, что вы не поверите, что он будет работать, пока не запустите его.

Кроме того, оригинальная статья дает хорошее объяснение того, как он достиг окончательного алгоритма.

Answer 6

MATLAB:

• Способ мошенничества (с использованием встроенной функции NCHOOSEK ): 13 символов, O (?)

  nchoosek(N,k)
  

• Мое решение: 36 символов, O (мин (k, N-k))

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

Answer 7

Учитывая разумное количество значений для n и K, рассчитайте их заранее и используйте справочную таблицу.

Это уклоняется от проблемы некоторым способом (вы разгружаете вычисления), но это полезный метод, если вам нужно определить большое количество значений.