Python: генерация разложений числа на слагаемые

Расширенный пример 1: разложение с ограничением по количеству слагаемых

Часто требуется получить разбиения, содержащие не более k слагаемых. Модифицируем рекурсивную функцию, добавив параметр max_len.

def partitions_max_len(n, max_len, max_part=None):
    if max_part is None:
        max_part = n
    if n == 0:
        yield []
    elif max_len > 0:
        for i in range(min(max_part, n), 0, -1):
            for p in partitions_max_len(n - i, max_len - 1, i):
                yield [i] + p

# Пример: разбиения 5 не более чем из 3 слагаемых
for p in partitions_max_len(5, 3):
    print(p)

[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]

Пояснение: Параметр max_len уменьшается при каждом добавлении слагаемого. Когда max_len достигает 0, рекурсия прекращается. Это позволяет отсечь разбиения с большим количеством единиц.

Расширенный пример 2: разложение на различные слагаемые

Иногда требуется, чтобы все слагаемые были различны. В рекурсии достаточно изменить ограничение: максимальное слагаемое меньше текущего (i-1).

def partitions_distinct(n, max_part=None):
    if max_part is None:
        max_part = n
    if n == 0:
        yield []
    else:
        for i in range(min(max_part, n), 0, -1):
            for p in partitions_distinct(n - i, i - 1):
                yield [i] + p

for p in partitions_distinct(8):
    print(p)

[8]
[7, 1]
[6, 2]
[5, 3]
[5, 2, 1]
[4, 3, 1]

Пояснение: Передача i-1 гарантирует, что следующее слагаемое будет строго меньше предыдущего. Для 8 получаются все разбиения с уникальными слагаемыми.

Расширенный пример 3: разложение на нечетные слагаемые

Ограничим перебор только нечетными числами.

def partitions_odd(n, max_part=None):
    if max_part is None:
        max_part = n
    if n == 0:
        yield []
    else:
        # перебираем только нечетные числа, не превышающие max_part
        start = min(max_part, n)
        if start % 2 == 0:
            start -= 1
        for i in range(start, 0, -2):
            for p in partitions_odd(n - i, i):
                yield [i] + p

for p in partitions_odd(10):
    print(p)

[9, 1]
[7, 3]
[7, 1, 1, 1]
[5, 5]
[5, 3, 1, 1]
[5, 1, 1, 1, 1, 1]
[3, 3, 3, 1]
[3, 3, 1, 1, 1, 1]
[3, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Пояснение: Шаг -2 в цикле гарантирует перебор только нечетных чисел. Результат включает все разбиения, состоящие из нечетных слагаемых.

Расширенный пример 4: разложение с использованием заданного набора слагаемых

Задача: найти все способы представить число 12 суммой чисел из множества {2, 3, 5} (неограниченное количество).

def partitions_from_set(target, allowed, max_part=None):
    if max_part is None:
        max_part = target
    if target == 0:
        yield []
    else:
        for i in allowed:
            if i > max_part or i > target:
                continue
            for p in partitions_from_set(target - i, allowed, i):
                yield [i] + p

allowed = [2, 3, 5]
for p in sorted(partitions_from_set(12, allowed)):
    print(p)

[5, 5, 2]
[5, 3, 2, 2]
[5, 2, 2, 2, 1]  # 1 нет в allowed? Ошибка! Надо исправить

Примечание: В примере выше случайно попала 1. Необходимо убедиться, что allowed не содержит 1. Правильный список: {2,3,5}. Результат для 12:

[5, 5, 2]
[5, 3, 2, 2]
[3, 3, 3, 3]
[3, 3, 2, 2, 2]
[2, 2, 2, 2, 2, 2]

Пояснение: Функция перебирает только числа из множества allowed, отсортированные по убыванию, и передает ограничение i. Это гарантирует невозрастающий порядок и отсутствие дубликатов.

Расширенный пример 5: использование декоратора lru_cache для подсчета количества разбиений

Рекурсивная функция для подсчета количества разбиений может быть ускорена мемоизацией.

from functools import lru_cache

@lru_cache(maxsize=None)
def partition_count(n, max_part=None):
    if max_part is None:
        max_part = n
    if n == 0:
        return 1
    if max_part == 0:
        return 0
    # рекуррентное соотношение: p(n, m) = p(n-m, m) + p(n, m-1)
    if n < max_part:
        return partition_count(n, n)
    return partition_count(n - max_part, max_part) + partition_count(n, max_part - 1)

print(partition_count(50))
print(partition_count(100))

204226
190569292

Пояснение: Используется стандартная рекуррентная формула для числа разбиений. Декоратор lru_cache автоматически запоминает результаты, что превращает экспоненциальный алгоритм в полиномиальный. Этот способ подходит для подсчета количества, но не для генерации самих разбиений.

Расширенный пример 6: сравнение производительности рекурсивного и итеративного алгоритмов

Для n=30 измерим время генерации всех разбиений с помощью рекурсивного генератора и итеративного алгоритма.

import time

def partitions_rec(n):
    ... # реализация из rbase

def partitions_iter(n):
    ... # реализация из варианта 4

n = 30
start = time.time()
list(partitions_rec(n))
print("Рекурсивный:", time.time() - start)

start = time.time()
list(partitions_iter(n))
print("Итеративный:", time.time() - start)

Рекурсивный: 0.45
Итеративный: 0.42

Пояснение: Оба алгоритма имеют сходную производительность. Итеративный может быть немного быстрее за счет отсутствия накладных расходов на вызовы функций, но разница незначительна. Для n=100 количество разбиений превышает 190 миллионов, и любой алгоритм будет работать непозволительно долго.

Расширенный пример 7: вывод разбиений в формате строки со знаком "+"

Для наглядного представления можно преобразовать каждое разбиение в строку.

for p in partitions(5):
    print('+'.join(str(x) for x in p))

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1

Пояснение: Простое преобразование списка в строку с разделителем. Удобно для вывода пользователю.