Теория числа разделов с Python - PullRequest
Новая
       6

Теория числа разделов с Python

0 голосов
/ 08 января 2019

Дано целое число для вычисления общего числа возможных способов представления итогов. Требуемая сумма равна 5, а целые числа можно рассматривать как [1,2,3]

5 способов получить целевую сумму: 

1 + 1 + 1 + 1 + 1 = 5

1 + 1 + 1 + 2 = 5

1 + 2 + 2 = 5

1 + 1 + 3 = 5

2 + 3 = 5

Ввод 5, 3, где 3 - диапазон [1,2,3] для достижения 5

Выход 5

Ответы [ 2 ]

0 голосов
/ 08 января 2019

Поскольку ваш вопрос требует только число возможностей, а не самих возможностей, это один из самых быстрых способов сделать это: 

def partitions(n, m):
    if n <= 1:
        return 1
    if m > n:
        return partitions(n, n)

    total = 0
    for i in range(1, m + 1):
        total += partitions(n - i, i)

    return total

Здесь n - это число, которое вы пытаетесь разделить, а m - ограничение на наибольшее число. Он обрабатывает даже очень большие числа очень быстро: 

In [1]: def partitions(n, m):
   ...:     if n <= 1:
   ...:         return 1
   ...:     if m > n:
   ...:         return(partitions(n, n))
   ...:
   ...:     total = 0
   ...:     for i in range(1, m + 1):
   ...:         total += partitions(n - i, i)
   ...:
   ...:     return total
   ...:

In [2]: partitions(5, 3)
Out[2]: 5

In [3]: partitions(10, 5)
Out[3]: 30

In [4]: partitions(50, 30)
Out[4]: 202139 # returned in less than a second
0 голосов
/ 08 января 2019

Я не думаю, что использование combinations() сработает здесь - функция возвращает комбинации массива, который вы передаете, но не создает дубликатов какого-либо данного элемента. Вы можете обойти это, используя вариант combinations_with_replacement(), но даже в этом случае у вас будет избыток недопустимых комбинаций, и для длинных списков время выполнения станет неразрешимым.

Вместо этого рассмотрим рекурсивное решение, подобное следующему. 

def reps(target, nums):
     res = []
     for i, v in enumerate(nums):
         if target - v > 0:
             res += [[v] + l for l in reps(target-v, nums[i:])]
         elif target - v == 0:
             res += [[v]]
     return res

Здесь я беру целевую сумму и список чисел и пытаюсь вычесть каждое число из цели. Если разница точно равна 0, я добавляю это последнее значение в список. Если оно больше нуля, я продолжаю пытаться добавить элементы в список, вызывая reps() с новым целевым значением и подмножеством исходных чисел, которое предотвращает перестановки одного и того же ответа. Я объединяю все это, добавляю предварительно выбранное значение из списка и продолжаю таким образом, пока не будет составлен список всех комбинаций.

Результат для вашего примера target=5 и nums=[1,2,3] - 

[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [2, 3]]
...