Partition Number in Java

在本节中，我们将学习什么是分区数，并创建Java 程序来检查给定数字是否为分区数。分区数程序经常出现在 Java 编码面试和学术中。

分区数

在组合学和数论中，将数字 K（大于 0）分区意味着将数字 K 写成正整数之和。分区数也称为整数分区。请注意，在进行分区时，求和项的顺序无关紧要。让我们通过一个例子来理解它。

方法

我们按排序顺序显示所有分区，并且分区内的数字也按排序顺序打印。其思想是借助当前分区中的值来实现下一个分区。

我们将每个分区存储在数组 ptt[] 中。我们将数组 ptt[] 初始化为 K，其中 K 是输入数字。在每次迭代中，我们首先打印 ptt[]，然后更新数组 ptt[] 以保留下一个分区。因此，我们的问题就简化为从当前分区找到下一个分区。

借助当前位置查找下一个分区数的步骤

当前分区存在于数组 ptt[] 中，并且其大小也已知。我们需要更新 ptt[] 以保留下一个分区。ptt[] 中的值应按非递增顺序排序。

步骤 1：查找数组 ptt[] 中最右边的非 1 值，并将该非 1 值之前遇到的 1 的计数保存在变量 r_val 中（它显示需要更新的右侧值的总和）。假设非 1 值的索引为 i。

步骤 2：将 ptt[i] 的值减一，并将 r_val 加一。现在可能有以下两种情况

1. 如果 ptt[i] 大于或等于 r_val。这是一个简单的情况（我们在新分区中已获得排序顺序）。将 r_val 放在 ptt[i + 1] 处，ptt[0…i + 1] 即为新分区。
2. 否则（这是一个有趣的情况，以 {3, 1, 1, 1} 作为初始 ptt[]，ptt[i] 从 3 减至 2，r_val 从 3 增至 4，因此，下一个分区将是 {2, 2, 2}）。

步骤 3：将 ptt[i] 复制到下一个位置，递增 i，并在 ptt[i] 小于 r_val 时减去 ptt[i] 的计数。最后，将 r_val 放在 ptt[i + 1] 处，p[0…i + 1] 即为新分区。此步骤类似于将 r_val 分割成 ptt[i] 的项（4 被分割成 2）。

分区数示例

令 K = 4，则 K 可以写成：

4 = 4 第一种方式

3 + 1 = 4 第二种方式（不考虑 1 + 3，因为求和项的顺序对分区没有影响）

2 + 2 = 4 第三种方式

2 + 1 + 1 = 4 第四种方式（同样，不考虑 1 + 2 + 1, 1 + 1 + 2）

1 + 1 + 1 + 1 = 4 第五种方式

因此，有五种唯一的方式来分割数字 4。下图显示了从 1 到 6 的数字分区。

分区数 Java 程序

让我们观察 Java 程序。

文件名：PartitionNumberExample.java

输出

All the Unique Partitions of 2 are: 
2 
1 1 

All the Unique Partitions of 3 are: 
3 
2 1 
1 1 1 

All the Unique Partitions of 4 are: 
4 
3 1 
2 2 
2 1 1 
1 1 1 1 

All the Unique Partitions of 5 are: 
5 
4 1 
3 2 
3 1 1 
2 2 1 
2 1 1 1 
1 1 1 1 1

说明： Java 程序基于上述方法。这里的关键是在进行分区时保持非递增顺序，并在发生违规时，在程序开始之前遵循上面定义的步骤 2 和步骤 3。