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

Я бы подошел к этому так:

Во-первых, обобщите проблему. Вы можете определить функцию

printPartitions(int target, int maxValue, string suffix)

со спецификацией:

Выведите все целочисленные разделы цели, за которыми следует суффикс, так что каждое значение в разделе не больше maxValue

Обратите внимание, что всегда существует по крайней мере 1 решение (при условии, что и target, и maxValue положительны), то есть все 1 с.

Вы можете использовать этот метод рекурсивно. Итак, давайте сначала подумаем о базовом случае:

printPartitions(0, maxValue, suffix)

следует просто напечатать suffix.

Если target не 0, у вас есть варианты: либо использовать maxValue, либо нет (если maxValue > target есть только один вариант: не использовать его). Если вы не используете его, вы должны уменьшить maxValue на 1.

То есть:

if (maxValue <= target)
    printPartitions(target-maxValue, maxValue, maxValue + suffix);
if (maxValue > 1)
    printPartitions(target, maxValue-1, suffix);

Объединение всего этого приводит к относительно простому методу (здесь закодировано на Java, и я немного изменил порядок операторов, чтобы получить тот же порядок, который вы описали):

void printPartitions(int target, int maxValue, String suffix) {
    if (target == 0)
        System.out.println(suffix);
    else {
        if (maxValue > 1)
            printPartitions(target, maxValue-1, suffix);
        if (maxValue <= target)
            printPartitions(target-maxValue, maxValue, maxValue + " " + suffix);
    }
}

Вы можете просто назвать это как

printPartitions(4, 4, "");

который выводит

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

Это частично основано на подходе Хьюстера.

Во-первых, обратите внимание, что последние числа вывода 1,2,2,3,4. Если последнее число 2, 2-е последние числа 1,2. Это говорит мне о том, что было бы неплохо иметь рекурсивную функцию с циклом for, генерирующим строку сзади.

Сам код довольно прост:

• Цикл от 1 до target, добавление переменной к суффиксу, вычитание его из target и рекурсия.
• Также обратите внимание, что каждая сгенерированная строка сортируется (что неявно позволяет избежать дублирования вывода). Мы сортируем его, просто передавая последнее сгенерированное число и не зацикливаясь дальше этого числа.

Код:

private void printPartitions(int target, int max, String suffix)
{
    if (target == 0)
       System.out.println(suffix);
    else
    {
       for (int i = 1; i <= max && i <= target; i++)
          printPartitions(target - i, i, i + " " + suffix);
    }
}

Функция вызывающего абонента:

public void printPartitions(int target)
{
   printPartitions(target, target, "");
}

Процесс перечисления целочисленных разделов числа n является рекурсивным. Существует единственный раздел 0, пустой набор (). Существует единственный раздел 1, набор (1). Есть два раздела 2, наборы (1 1) и (2). Есть три раздела 3, наборы (1 1 1), (1 2) и (3). Есть пять разделов числа 4, множества (1 1 1 1), (1 1 2), (1 3), (2 2) и (4). Есть семь разделов числа 5, наборы (1 1 1 1 1), (1 1 1 2), (1 2 2), (1 1 3), (1 4), (2 3) и (5). И так далее. В каждом случае следующий больший набор разделов определяется путем добавления каждого целого числа x, меньшего или равного n, ко всем наборам, образованным разделением n – x, устраняя любые дубликаты.

Я даю код на нескольких языках в моем блоге. Например, вот мое решение на схеме:

(define (set-cons x xs)
  (if (member x xs) xs
    (cons x xs)))

(define (parts n)
  (if (zero? n) (list (list))
    (let ((xs (list)))
      (do ((x 1 (+ x 1))) ((= x n) (cons (list n) xs))
        (do ((yss (parts (- n x)) (cdr yss))) ((null? yss))
          (set! xs (set-cons (sort < (cons x (car yss))) xs)))))))

> (parts 0)
(())
> (parts 1)
((1))
> (parts 2)
((2) (1 1))
> (parts 3)
((3) (1 1 1) (1 2))
> (parts 4)
((4) (2 2) (1 1 2) (1 1 1 1) (1 3))
> (parts 5)
((5) (2 3) (1 1 3) (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 4))
> (parts 6)
((6) (3 3) (2 2 2) (2 4) (1 1 4) (1 1 2 2) (1 1 1 1 2)
  ((1 1 1 1 1 1) (1 1 1 3) (1 2 3) (1 5))

вот алгоритм. дайте мне знать, что вы думаете. проверено на питоне3

def partition(A):
    table = [[[1]]] + [None]*(A-1)
    for i in range(1,A):
        table[i] = [[i+1]]
        for k in range(i):
            table[i].extend([[i-k]+l for l in table[k] if i-k >= l[0]])
    return table[-1]

def print_partition(A):
    for i in reversed(partition(A)): print(*i)