Я пытаюсь найти способ отображения всех возможных наборов X-целых чисел, которые суммируются с заданным целым числом. например, чтобы получить все 2 целых множества, которые составляют 5, я бы:
1, 4
2, 3
Или для 3 целых чисел, которые делают 6:
1, 1, 4
1, 2, 3
2, 2, 2
Мне нужны только целые числа, не считая 0, и ему нужно работать только до 15 в наборе и 30 макс. число.
Я даже не уверен, имеет ли это термин математически. Это похоже на факторизацию, я думаю?
Вот один из способов решения этой проблемы:
def sum_to_n(n, size, limit=None):
"""Produce all lists of `size` positive integers in decreasing order
that add up to `n`."""
if size == 1:
yield [n]
return
if limit is None:
limit = n
start = (n + size - 1) // size
stop = min(limit, n - size + 1) + 1
for i in range(start, stop):
for tail in sum_to_n(n - i, size - 1, i):
yield [i] + tail
Вы можете использовать его так.
for partition in sum_to_n(6, 3):
print partition
[2, 2, 2]
[3, 2, 1]
[4, 1, 1]
http://en.wikipedia.org/wiki/Partition_(number_theory)
Вот фрагмент здесь:
from itertools import combinations, chain
def sum_to_n(n):
'Generate the series of +ve integer lists which sum to a +ve integer, n.'
from operator import sub
b, mid, e = [0], list(range(1, n)), [n]
splits = (d for i in range(n) for d in combinations(mid, i))
return (list(map(sub, chain(s, e), chain(b, s))) for s in splits)
Используйте его следующим образом:
for p in sum_to_n(4):
print p
Выходы:
[4] [1, 3] [2, 2] [3, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [1, 1, 1, 1]
Они называются разделами целого числа, о котором идет речь. Другие предоставили ссылки для их определения.
Трюк, чтобы делать эти вещи, часто делает их рекурсивно. Например, предположим, что я хотел сформировать все четкие способы построения 10 в виде суммы ровно трех целых чисел, ни одна из которых не появляется более одного раза.
Посмотрите на максимально возможный компонент этой суммы. Может ли это быть 10? Нет, поскольку, если самый большой компонент равен 10, то что остается? Т.е., 10 - 10 = 0. Оказывается, если наибольший элемент в сумме равен 7, то то, что остается, должно быть разбито на сумму двух натуральных чисел, равно 3. И мы можем разбить 3 на сумму двух отличные целые числа одним способом. Итак, {7,2,1} - такой раздел и единственный раздел, который включает в себя элемент размером 7.
Может ли 6 использоваться как самый большой элемент? Если да, то у нас осталось бы 4. И мы можем разбить 4 точно в одном направлении, чтобы получить разбиение {6,3,1}. Дальнейший поиск даст другие разделы из 10 как {5,4,1}, {5,3,2}. Никто не может существовать.
Дело в том, что эту операцию легко определить как рекурсивную функцию. При тщательном кодировании можно даже использовать memoization, чтобы избежать повторного вычисления того, что мы видели раньше.
Ваш вопрос можно перефразировать следующим образом:
Учитывая число N, найдите все множества [S1, S2, S3.....], где сумма каждого множества равна N. Размер множеств задается числом L.
Сначала рассмотрим случай L=2. Это означает, что вы можете иметь следующие наборы
(9,1) , (8,2), (7,3) , (6,4) , (5,5)
Я назову это базовым решением, и вы скоро поймете, почему.
Теперь изменим наш L на 3 и повторим наш ответ:
Итак, рассмотрим число 9. Существует ли такой список L такой, что sum(L) + 9 = 10? Очевидный ответ - нет, но интересный здесь не ответ, а сам вопрос. Мы в основном запрашиваем набор элементов 2, которые можно суммировать как число 1. Это та же проблема, которая была решена базовым решением.
Итак, поэтому для каждого числа x в [9,8,7,6,5,4,3,2,1] вы пытаетесь найти набор [a,b] такой, что x+a+b = 10.
Это не полный ответ, но идея состоит в том, что вы видите шаблон здесь и используете рекурсию, чтобы вычислить базовый случай, как сделано выше, а затем выяснить рекурсивный вызов, который завершит ваше решение. Удачи!