Получите все числа, которые составляют в целом число
Я пытаюсь найти способ отобразить все возможные наборы X целых чисел, которые составляют в целом данное целое число. например, для получения всех 2 целочисленных наборов, которые делают 5, я имел бы:
1, 4
2, 3
Или для 3 целых чисел, которые делают 6:
1, 1, 4
1, 2, 3
2, 2, 2
Мне только нужны целые числа не включая 0, и это только должно продолжить работать приблизительно до 15 в наборе и 30 максимум число.
Я даже не уверен, имеет ли это термин математически. Это подобно факторизации, которую я предполагаю?
3 ответа
Вот один из способов решения этой проблемы:
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]
Там есть фрагмент здесь :
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, чтобы не повторно вычислять это, которое мы видели прежде.