Сгенерируйте все возможные списки длины N, которые суммируются с S в Python

Question

Сгенерируйте все возможные списки длины N, которые суммируются с S в Python

Я пытаюсь сгенерировать все возможные списки длины N, которые суммируются с S. Я написал код для этого, но для чего-то большого (в частности, я хочу N = 5, S = 100), я сталкиваюсь с ошибками переполнения памяти.

Я ищу либо лучшее решение проблемы, либо способ улучшить свой код, чтобы запустить его на N = 5, S = 100. Эти две программы, представленные ниже, работают в тандеме, чтобы создать все возможные комбинации чисел во вложенных списках, а затем переработать их, чтобы они соответствовали правильному формату. Некоторые образцы выходных данных воспроизводятся ниже.

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

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

def nToSum(N,S):
    ''' Creates a nested list of all possible lists of length N that sum to S'''
    if N <= 1: #base case
        return [S]
    else:
        L = []
        for x in range(S+1):   #create a sub-list for each possible entry of 0 to S 
            L += [[x,nToSum(N-1,S-x)]]  #create a sub-list for this value recursively
        return L

def compress(n=[],L): #designed to take in a list generated by nToSum
    '''takes the input from nToSum as list L, and then flattens it so that each list is a
       top level list.  Leading set n is the "prefix" list, and grows as you climb down the 
       sublists'''
    if type(L[0]) == int:  #base case:  you have exposed a pure integer
        return [n+L]       #take that integer, and prepend the leading set n
    else:
        Q = []
        for x in L:  # look at every sublist
            Q += compress(n+[x[0]],x[1])  # for each sublist, create top level lists recursively
        return Q                          # note:  append x[0] to leading set n

>>> nToSum(3,3)
[[0, [[0, [3]], [1, [2]], [2, [1]], [3, [0]]]], [1, [[0, [2]], [1, [1]], [2, [0]]]], [2, [[0, [1]], [1, [0]]]], [3, [[0, [0]]]]]

>>> compress([],nToSum(3,3))
[[0, 0, 3], [0, 1, 2], [0, 2, 1], [0, 3, 0], [1, 0, 2], [1, 1, 1], [1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]]

5

python list recursion sum

задан Nick2253 13 October 2011 в 01:40

1 ответ

Другие вопросы по тегам:

python list recursion sum

Похожие вопросы:

score 0 · Answer 1

Я искал что-то подобное этому вопросу, но с добавленной сложностью ограничений в опциях для каждого n N. Вот мой подход:

, Например, если мы ищем перестановки 5 чисел от 10 to 50, которые составляют в целом 100

def permutations_w_constraints(n_perm_elements, sum_total, min_value, max_value):
    # base case
    if n_perm_elements == 1:
        if (sum_total <= max_value) & (sum_total >= min_value):
            yield (sum_total,)
    else:
        for value in range(min_value, max_value + 1):
            for permutation in permutations_w_constraints(
                n_perm_elements - 1, sum_total - value, min_value, max_value
            ):
                yield (value,) + permutation

results = list(permutations_w_constraints(5, 100, 10, 50))

print('total permutations:',len(results))
for i in results[:10] + results[-10:]:
    print(i)

total permutations: 312676
(10, 10, 10, 20, 50)
(10, 10, 10, 21, 49)
(10, 10, 10, 22, 48)
(10, 10, 10, 23, 47)
(10, 10, 10, 24, 46)
(10, 10, 10, 25, 45)
(10, 10, 10, 26, 44)
(10, 10, 10, 27, 43)
(10, 10, 10, 28, 42)
(10, 10, 10, 29, 41)
(50, 18, 10, 10, 12)
(50, 18, 10, 11, 11)
(50, 18, 10, 12, 10)
(50, 18, 11, 10, 11)
(50, 18, 11, 11, 10)
(50, 18, 12, 10, 10)
(50, 19, 10, 10, 11)
(50, 19, 10, 11, 10)
(50, 19, 11, 10, 10)
(50, 20, 10, 10, 10)