Вернуть последовательность переменной длины, сумма которой равна заданному целому числу

Question

В форме f(x,y,z), где x - заданная целочисленная сумма, y - минимальная длина последовательности, а z - максимальная длина последовательности. Но сейчас давайте представим, что мы имеем дело с последовательностью фиксированной длины, потому что в противном случае мне понадобится много времени, чтобы написать вопрос.

Итак, наша функция - f(x,r), где x - заданная целочисленная сумма, а r - длина последовательности в списке возможных последовательностей.

Для x = 10 и r = 2 возможны следующие комбинации:

1 + 9
2 + 8
3 + 7
4 + 6
5 + 5

Давайте сохраним это в Python как список пар:

[(1,9), (2,8), (3,7), (4,6), (5,5)]

Таким образом, использование выглядит так:

>>> f(10,2)
[(1,9), (2,8), (3,7), (4,6), (5,5)]

Вернуться к исходному вопросу, где последовательность возвращается для каждой длины в диапазоне (y,x). В форме f(x,y,z), определенной ранее и не содержащей последовательности длиной 1 (где y-z == 0), это будет выглядеть так:

>>> f(10,1,3)
[{1: [(1,9), (2,8), (3,7), (4,6), (5,5)],
  2: [(1,1,8), (1,2,7), (1,3,6) ... (2,4,4) ...],
  3: [(1,1,1,7) ...]}]

Таким образом, вывод представляет собой список словарей, где значение представляет собой список пар. Не совсем оптимально.

Итак, мои вопросы:

1. Есть ли библиотека, которая уже обрабатывает это?
2. Если нет, может кто-нибудь помочь мне написать обе упомянутые функции? (сначала фиксированная длина последовательности)?
3. Из-за огромных пробелов в моих знаниях по тривиальной математике, не могли бы вы проигнорировать мой подход к целочисленному хранилищу и использовать любую структуру, которая наиболее целесообразна?

Извините за все эти арифметические вопросы сегодня. Спасибо!

Answer 1

Модуль itertools определенно пригодится, поскольку мы имеем дело с премуациями - однако это выглядит подозрительно как домашнее задание ...

Редактировать : Хотя это выглядит забавно, поэтому я попробую.

Редактировать 2 : Это то, что вы хотите?

from itertools import combinations_with_replacement
from pprint import pprint

f = lambda target_sum, length: [sequence for sequence in combinations_with_replacement(range(1, target_sum+1), length) if sum(sequence) == target_sum]

def f2(target_sum, min_length, max_length):
    sequences = {}
    for length in range(min_length, max_length + 1):
        sequence = f(target_sum, length)
        if len(sequence):
            sequences[length] = sequence
    return sequences

if __name__ == "__main__":
    print("f(10,2):")
    print(f(10,2))
    print()
    print("f(10,1,3)")
    pprint(f2(10,1,3))

Выход:

f(10,2):
[(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)]

f(10,1,3)
{1: [(10,)],
 2: [(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)],
 3: [(1, 1, 8),
     (1, 2, 7),
     (1, 3, 6),
     (1, 4, 5),
     (2, 2, 6),
     (2, 3, 5),
     (2, 4, 4),
     (3, 3, 4)]}

Answer 2

Проблема известна как Целочисленные разбиения и широко изучается.

Здесь вы можете найти статью, сравнивающую производительность нескольких алгоритмов (и предлагающую конкретный), но в сети много ссылок.

Answer 3

Я только что написал рекурсивную функцию генератора, вы должны выяснить, как получить список из нее самостоятельно ...

def f(x,y):
    if y == 1:
        yield (x, )
    elif y > 1:
        for head in range(1, x-y+2):
            for tail in f(x-head, y-1):
                yield tuple([head] + list(tail))

def f2(x,y,z):
    for u in range(y, z+1):
        for v in f(x, u):
            yield v

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