4

私はプログラミング演習を解いていて、満足に解決策を見つけることができない問題に出くわしました。問題は次のようになります。

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=4 の場合、出力は Output= である必要があります。

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

この問題を解決するにはどのように考えればよいでしょうか。再帰の使用について疑問に思っていました。誰かがこの質問のアルゴリズムを教えてくれますか? または解決へのヒント。そのような種類の問題についての説明は大歓迎です。(プログラミング初心者です) よろしくお願いします!!

4

4 に答える 4

3

これは、Heuster のアプローチから大まかに導き出されたものです。

まず、出力の最後の数字が であることに注意してください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, "");
}
于 2013-07-18T12:07:48.510 に答える
2

数値nの整数分割を列挙するプロセスは再帰的です。0 の単一のパーティション、空のセット () があります。1、セット (1) の単一のパーティションがあります。2 の 2 つのパーティション、セット (1 1) と (2) があります。3 の 3 つのパーティション、セット (1 1 1)、(1 2)、および (3) があります。4 の 5 つのパーティション、セット (1 1 1 1)、(1 1 2)、(1 3)、(2 2)、および (4) があります。5 の 7 つのパーティション、セット (1 1 1 1 1)、(1 1 1 2)、(1 2 2)、(1 1 3)、(1 4)、(2 3)、および (5) があります。等々。いずれの場合も、 n以下の各整数xをn − xの分割によって形成されるすべてのセットに追加し、重複を排除することによって、次に大きな分割のセットが決定されます。

私は自分のブログでいくつかの言語でコードを提供しています。たとえば、Scheme での私のソリューションは次のとおりです。

(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))
于 2013-07-18T12:40:33.487 に答える
1

ここにアルゴリズムがあります。どう考えているか教えてください。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)
于 2013-07-18T10:59:37.457 に答える