Получить все числа, которые складываются в число

Question

Я пытаюсь найти способ отобразить все возможные наборы целых чисел X, которые складываются в данное целое число. например, чтобы получить все 2 набора целых чисел, которые составляют 5, у меня будет:

1, 4
2, 3

Или для 3 целых чисел, которые составляют 6:

1, 1, 4
1, 2, 3
2, 2, 2

Мне нужны только целые числа, не включая 0, и ему нужно работать только до 15 в наборе и до 30 макс. число.

Я даже не уверен, имеет ли это термин математически. Я думаю, это похоже на факторизацию?

Answer 1

Вот один из способов решения этой проблемы:

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]

Answer 2

Здесь есть фрагмент здесь :

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]

Answer 3

Ваш вопрос можно перефразировать так:

Учитывая число 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.

Это не полный ответ, но идея в том, что вы видите образец здесь и используете рекурсию для вычисления базового случая, как сделано выше, а затем вычисляете рекурсивный вызов, который завершит ваше решение. Удачи!

Answer 4

Они называются разделами рассматриваемого целого числа. Другие предоставили ссылки для их определения.

Уловка, чтобы сделать эти вещи, часто делает их рекурсивно Например, предположим, что я хотел сформировать все различные способы построить 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}. Другие не могут существовать.

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