打印给定整数作为输入的所有唯一整数分区 [英] 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)

与规范:

打印target的所有整数分区，后跟后缀，使得分区中的每个值最多为maxValue

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

请注意，始终存在至少 1 个解(假设 target 和 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)

应该简单地打印 suffix.

如果 target 不是 0，您必须选择:使用 maxValue 或不使用(如果 maxValue > target 只有一个选项:不要使用它).如果你不使用它，你应该将 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);

---

将这一切结合起来会产生一个相对简单的方法(这里用 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);
    }
}

你可以简单地称之为

printPartitions(4, 4, "");

哪个输出

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

---

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

---

You can also choose to first create a list of all solutions and only print afterwards, like this:

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

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