Получение кумулятивных комбинаций (x выберите y) для убывающих значений x в упорядоченном последовательном списке

Question

У меня есть простой список list = [0,1,2,3,4,5,6,7,8,9,10,11,12]. Для любого значения x в списке (где x> = 4, чтобы избежать ошибки), мне нужно получить совокупное число возможных комбинаций «выбрать 4» для каждого значения y, где y < x.

Например, для x = list[7] Я хочу получить счет всех совокупных, выбрать 4 комбинации для чисел <= 7, 6, 5 и 4, то есть 7c4, 6c4, 5c4 и 4c4. Они оценивают до 35, 15, 5 и 1, таким образом, кумулятивный счет равен 56. </p>

Я могу сделать это, просто зациклив и получив комбинации:

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r) 
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

cumu_comb = 0
for i in list[:3:-1]:
    cumu_comb += ncr(i - 1, len(list) - i)

Это похоже на медленный/ метод грубой силы;со многими миллионами итераций это не будет идеальным. Существует ли математическое представление для нахождения совокупных комбинаций для всех значений

Answer 1

Вы можете легко решить эту проблему с помощью формулы комбинаций.

For that reason, it might be considered more of a математика вопрос, но я отвлекся.

Мы можем найти факториал числа, используя math.factorial() а не с петлей;так как это использует реализацию C, это будет намного быстрее.

Мы также можем использовать списки, чтобы сложить это в одну строку, хотя я поместил входы и выходы отдельно, они могли бы быть сгруппированы вместе. Имейте в виду, что я не буду представлять способ предотвращения ошибок в этом коде, поскольку этот вопрос подразумевает, что мы должны иметь возможность предположить, что все x больше 4.

Найтикумулятивный счет, который мы можем записать:

import math

x = int(input("x: "))
a = sum([math.factorial(i)/(math.factorial(4) * math.factorial(i - 4)) for i in n[4:x+1]])
print(a)

Например, если мы введем x как 7:

• , мы будем перебирать список [4, 5, 6, 7].
• Для каждого из этих элементов мы выполняем формулу комбинаций с k = 4 (как указано в вопросе, хотя это можно изменить в зависимости от обстоятельств, просто изменив 4),Это входит в список, из-за нашей итерации списка.
• Наконец все элементы суммируются.

Это можно описать как.

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