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

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+Выбрать+15000000

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

Любой язык приемлем.

Это было полезно?

Решение

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

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

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

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

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

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

РЕДАКТИРОВАТЬ2:Кроме того, как указано в другом ответе, значения легко переполнят двойное значение, поэтому тип с плавающей запятой с очень расширенной точностью необходимо будет использовать даже для умеренно больших значений k и 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 для вычисления приближения.Поскольку он не использует никакого внешнего цикла, а размер чисел ограничен, я думаю, он будет выполняться за О(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, вычислите их заранее и используйте справочную таблицу.

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

МАТЛАБ:

  • Способ мошенника (с помощью встроенной функции НЧООСЕК): 13 символов, О(?)

    nchoosek(N,k)

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

    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