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

Question

Я решал упражнение по программированию и сталкивался с проблемой, из-за которой я не смог удовлетворительно найти решение. Проблема состоит в следующем:

Print all unique integer partitions given an integer as input. 
Integer partition is a way of writing n as a sum of positive integers. 

напр: Input = то выход должен быть выход =

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

Как я должен думать о решении этой проблемы? Мне было интересно об использовании рекурсии. Может ли кто-нибудь предоставить мне алгоритм для этого вопроса? Или намек на решение. любое объяснение подобных проблем приветствуется. (Я новичок в мире программирования) Спасибо!

Answer 1

я бы подойти к нему так:

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

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 

Answer 2

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

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) 

Answer 3

Это слабо производным от Heuster's approach.

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

Сам код довольно прямолинеен:

• Loop от 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, ""); 
} 

Answer 4

Процесс для перечисления разбиений ряда п является рекурсивным. Существует один раздел 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). И так далее. В каждом случае на следующий больший набор разделов определяется путем добавления каждого целого х меньше, чем или равный п всех множеств, образованных разбиения п - х, устраняя любые дубликаты.

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

(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))