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

23

我会这样处理：

首先，概括问题。你可以定义一个函数

printPartitions(int target, int maxValue, string suffix)

与规范：

打印target的所有整数分区，后跟后缀，使得分区中的每个值最多为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

您还可以选择先创建所有解决方案的列表，然后再打印，如下所示：

function createPartitions(target, maxValue, suffix, partitions) {
  if (target == 0) {
    partitions.push(suffix);
  } else {
    if (maxValue > 1)
      createPartitions(target, maxValue-1, suffix, partitions);
    if (maxValue <= target)
      createPartitions(target-maxValue, maxValue, [maxValue, ...suffix], partitions);
  }
}

const partitions = [];
createPartitions(4, 4, [], partitions);
console.log(partitions);

于 2013-07-18T10:49:16.020 回答
3

这大致源自Heuster 的方法。

首先，请注意输出的最后一个数字是1,2,2,3,4。如果最后一个数字是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 的两个分区，集合 (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)。等等。在每种情况下，下一个更大的分区集合是通过将每个小于或等于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 回答