Вывести все возможные распределения сумм n в m пробелов

Question

Например, сумма 3 в 4 пробела будет равна:

3 0 0 0, 
0 3 0 0,
0 0 3 0,
0 0 0 3,
0 1 1 1,
1 0 1 1,
1 1 0 1,
1 1 1 0,
2 1 0 0,
... 

или сумма 3 в 2 пробела будет:

2 1
1 2
0 3
3 0

Answer 1

Последовательности, которые вы ищете, называются составы .

Нахождение композиции из числа n эквивалентно выбору индексов в интервале от 0 до *1007 п * .Вы восстанавливаете композицию, получая расстояние между последовательными выбранными индексами.

Пример

Учитывая число n = 3 , нам нужна композиция длиной 4 .

Первые два индекса должны быть 0 и 3 , поскольку это наш диапазон.Затем мы выбираем еще три индекса в интервале [0, 1, 2, 3] , чтобы получить ровно 4 пробелов.

[0, 1, 2, 3]
 ^     ^  ^
       ^  ^

Мы таким образом выбрали 0, 2, 2, 3, 3 .Мы восстанавливаем композицию, получая расстояние между последовательными индексами.То есть [2, 0, 1, 0] .

Это соответствует взятию комбинации с заменой чисел от 0 до 3 .Таким образом, мы можем использовать itertools.combinations_with_replacement и перевести каждую такую ​​комбинацию в соответствующую композицию.

Код

def compositions(sum_, n):
    for indices in combinations_with_replacement(range(sum_ + 1), n - 1):
        yield [b - a for a, b in zip([0, *indices], [*indices, sum_])]

print(*compositions(3, 4))

Выход

[0, 0, 0, 3]
[0, 0, 1, 2]
[0, 0, 2, 1]
[0, 0, 3, 0]
[0, 1, 0, 2]
[0, 1, 1, 1]
[0, 1, 2, 0]
[0, 2, 0, 1]
[0, 2, 1, 0]
[0, 3, 0, 0]
[1, 0, 0, 2]
[1, 0, 1, 1]
[1, 0, 2, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 2, 0, 0]
[2, 0, 0, 1]
[2, 0, 1, 0]
[2, 1, 0, 0]
[3, 0, 0, 0]

Answer 2

Используя itertools.product и filter, создайте все возможности, а затем отфильтруйте те, чья сумма равна 3

from itertools import product

lst = [0, 1, 2, 3]
print(list(filter(lambda x: sum(x) == 3, product(lst, repeat = 4))))
print(list(filter(lambda x: sum(x) == 3, product(lst, repeat = 2))))