Рекурсивная комбинация Python

Question

Как я могу написать функцию, которая вычисляет:

C(n,k)= 1                          if k=0
        0                          if n<k
        C(n-1,k-1)+C(n-1,k)     otherwise

Пока что у меня есть:

def choose(n,k):
if k==0:
   return 1
elif n<k:
   return 0
else:

Answer 1

Предполагая, что отсутствующие операнды в вашем вопросе являются операторами вычитания (спасибо lejlot), это должен быть ответ:

def choose(n,k):
  if k==0:
     return 1
  elif n<k:
     return 0
  else:
     return choose(n-1, k-1) + choose(n-1, k)

Обратите внимание, что в большинстве систем Python максимальная глубина или предел рекурсии составляет всего 1000. После этого это вызовет исключение. Возможно, вам придется обойти это путем преобразования этой рекурсивной функции в итеративную.

Вот пример итеративной функции, которая использует стек для имитации рекурсии, избегая при этом максимального предела рекурсии Python:

def choose_iterative(n, k):
  stack = []
  stack.append((n, k))
  combinations = 0

  while len(stack):
    n, k = stack.pop()
    if k == 0:
      combinations += 1
    elif n<k:
      combinations += 0 #or just replace this line with `pass`
    else:
      stack.append((n-1, k))
      stack.append((n-1, k-1))

  return combinations    

Answer 2

Решение из Википедии ( http://en.wikipedia.org/wiki/Binomial_coefficient)

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if k > n - k: # take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
        return 1
    return choose(n-1, k) + choose(n-1, k-1)

Answer 3

Улучшение от экспоненциального до линейного времени

Все ответы, приведенные до сих пор, показывают экспоненциальное время. O(2n), Тем не менее, это можно сделать в O(k) изменив одну строку кода.

---

Объяснение:

Причиной экспоненциального времени выполнения является то, что каждая рекурсия разделяет проблему на перекрывающиеся подзадачи с этой строкой кода ( см. Ideone здесь):

def choose(n, k):
    ...
    return choose(n-1, k-1) + choose(n-1, k)

Чтобы понять, почему это так плохо, рассмотрим пример choose(500, 2), Числовое значение 500 choose 2 является 500*499/2; однако, используя рекурсию выше, требуется 250499 рекурсивные вызовы, чтобы вычислить это. Очевидно, что это излишне, так как требуется всего 3 операции.

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

Например, следующая рекурсия эквивалентна, но использует только 3 рекурсивные вызовы для вычисления choose(500,2) ( см. Ideone здесь):

def choose(n,k):
    ...
    return ((n + 1 - k)/k)*choose(n, k-1)

Причина улучшения заключается в том, что каждая рекурсия имеет только одну подзадачу, которая уменьшает k от 1 с каждым звонком. Это означает, что мы гарантируем, что эта рекурсия займет только k + 1 рекурсии или O(k), Это огромное улучшение для изменения одной строки кода!

Если вы хотите сделать еще один шаг вперед, вы можете воспользоваться симметрией в "n выберите k", чтобы убедиться, что k <= n/2 ( см. Ideone здесь):

def choose(n,k):
    ...
    k = k if k <= n/2 else n - k            # if k > n/2 it's equivalent to k - n
    return ((n + 1 - k)/k)*choose(n, k-1)

Answer 4

Вы пытаетесь вычислить количество вариантов, чтобы выбрать k из n элементов:

def choose(n,k):
    if k == 0: 
       return 1 # there's only one option to choose zero items out of n
    elif n < k:
       return 0 # there's no way to choose k of n when k > n
    else:
        # The recursion: you can do either
        # 1. choose the n-th element and then the rest k-1 out of n-1
        # 2. or choose all the k elements out of n-1 (not choose the n-th element)
        return choose(n-1, k-1) + choose(n-1, k)

Answer 5

Именно так

def choose(n,k):
    if k==0:
        return 1
    elif n<k:
        return 0
    else:
        return choose(n-1,k-1)+choose(n-1,k)

РЕДАКТИРОВАТЬ

Это простой способ, для эффективного взглянуть на wikipedia и spencerlyon2 answer