Java 中的下一个排列

要确定序列元素的字典序“下一个排列”，请应用下一个排列方法。它指的是将数组中的项按字典序重新排列成下一个更大的排列。重新排列项以生成字典序的下一个排列是下一个排列算法的基础。

目标是给定一个元素数组，确定字典序的下一个排列。在本节中，我们将讨论在 Java 中实现下一个排列算法的两种不同方法：使用**内置函数**和使用**新的交换和反转函数**。

查找下一个排列的步骤

1. 选择要交换的第一个组件

从右端开始，在数组中找到第一个小于下一个元素（nums[i + 1]）的元素（nums[i]）。

2. 识别右侧的最小元素

如果找到这样的元素 nums[i]，则再次从右向左扫描数组，找到 nums[i] 右侧大于 nums[i] 的最小元素。

3. 交换两个组件

用已识别的元素替换 nums[i]，确保新排列比之前的排列更大。

4. 反转右侧的子数组

在原始元素 (nums[i]) 的右侧反转子数组。通过确保数组的其余部分按升序排列，此步骤可产生字典序的最小下一个排列。

方法 1：使用 swap() 和 reverse() 函数

让我们首先指出，当前排列被修改为字典序更大，从而导致下一个排列。

• 通过查找最长的非递增后缀来定位枢轴。
• 如果后缀包含整个数组，则不存在更高阶的排列。
• 从末尾遍历以查找枢轴最右侧的后继项。
• 交换枢轴和后继项。
• 为了保证递增顺序，反转后缀。

NextPermutation.java

输出

[100, 300, 200]

方法 2：通过使用内置函数

NextPermutationBuiltIn.java

输出

[10, 30, 20]

结论

总之，理解和应用 Java 中的下一个排列算法为算法推理和数组管理提供了重要的见解。为了生成下一个字典序更大的排列，目标是找到一个准确且最优的解决方案，无论是使用内置算法还是自定义函数。