打印给出一个整数作为输入的所有唯一的整数分区 [英] Print all unique integer partitions given an integer as input

问题描述

我解决一个编程练习和碰到过这我不能够令人满意地找到解决的问题。 问题就如下：

I was solving a programming exercise and came across a problem over which I am not able to satisfactorily find a solution. The problem goes as follows:

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

为前：     输入= 4 然后输出应     输出=

for ex: Input=4 then output should be Output=

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

我应该如何考虑解决这个问题呢？ 我想知道如何使用递归。任何人都可以向我提供的算法，这个问题的？ 或者对解决方案的提示。 对于这样那样的问题作出解释是值得欢迎的。 （我在编程世界的初学者） 谢谢！！

How should I think about solving this problem? I was wondering about using recursion. Can anyone provide me an algorithm for this question? Or a hint towards solution. any explanation for such kind of problems is welcome. (I am a beginner in programming world) Thank you!!

推荐答案

我会接近这种方式：

首先，推广的问题。您可以定义一个函数

First, generalize the problem. You can define a function

printPartitions(int target, int maxValue, string suffix)

与规格：

打印所有整数目标的分区，随后后缀，使得所述分区中的每个值是至多包括maxValue

Print all integer partitions of target, followed by suffix, such that each value in the partition is at most maxValue

请注意总是有至少1溶液（提供既靶和包括maxValue是正），其是全1

Note that there is always at least 1 solution (provided both target and maxValue are positive), which is all 1s.

您可以递归地使用这种方法。所以让我们先想一下基本情况：

You can use this method recursively. So lets first think about the base case:

printPartitions(0, maxValue, suffix)

应该简单地打印后缀。

如果目标不是 0 ，你必须选择：要么使用 maxValue（最大值）或没有（如果 maxValue分别＆GT;目标只有一个选择：不使用它）。如果你不使用它，你应该降低 maxValue（最大值）按 1 。

If target is not 0, you have to options: either use maxValue or not (if maxValue > target there is only one option: don't use it). If you don't use it, you should lower maxValue by 1.

这就是：

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

---

结合这一切都导致了一个比较简单的方法（codeD中的Java在这里，我重新排序的语句，你介绍它来获得同样的顺序）：

---

Combining this all leads to a relatively simple method (coded in Java here and I reordered the statements a little to obtain the very same order as you described):

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);
    }
}

您可以简单地把这个作为

You can simply call this as

printPartitions(4, 4, "");

它输出

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

这篇关于打印给出一个整数作为输入的所有唯一的整数分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！