C++实现下一个排列算法代码错误 输入[2,3,1]输出不符预期

核心问题 #

你的实现思路完全正确，bug出在第二个查找交换元素的for循环里，break语句的位置写错了。

错误复现（以输入[2,3,1]为例） #

1. 第一步查找index的逻辑执行正常：从后往前遍历，找到index=0（对应元素2，小于右侧相邻的3），这一步符合预期。
2. 执行第二个查找j的循环时，错误代码如下：

   for (int i = nums.size() - 1; i >= index + 1; i--)
   {
       if(nums[i] > nums[index])
       {
           j = i;
       }
       break; // 错误点：break写在了if判断外部
   }
   

   这个写法会导致循环无论if条件是否成立，第一次执行完判断就直接触发break终止，完全不会完成从后往前遍历查找的流程。
   对[2,3,1]来说，循环第一次i=2（对应元素1），判断1>2不成立，j不会被重新赋值，保留初始化的j=2（数组末尾位置），随后直接退出循环。
3. 后续执行swap(nums[0], nums[2])，数组变为[1,3,2]，再反转index+1位置后的子段[3,2]得到[2,3]，最终输出错误结果[1,2,3]。

修复方法 #

把break移动到if代码块内部，只有找到符合条件的元素时，才给j赋值并退出循环。

注：因为index位置是从后往前找到的第一个满足nums[i-1]<nums[i]的位置，index后的子段本身是非升序排列的，所以从后往前找到的第一个大于nums[index]的元素，就是恰好比nums[index]大的最小元素，这个逻辑本身没有问题。

修正后的查找j的代码段：

for (int i = nums.size() - 1; i >= index + 1; i--)
{
    if(nums[i] > nums[index])
    {
        j = i;
        break; // 找到目标才终止循环
    }
}

修复后验证 #

用输入[2,3,1]测试：

1. 找到index=0后，循环i从2开始遍历：i=2对应元素1，不满足大于2，继续往前；i=1对应元素3，满足大于2，赋值j=1后退出循环。
2. 交换nums[0]和nums[1]，数组变为[3,2,1]。
3. 反转位置1之后的子段[2,1]得到[1,2]，最终数组为[3,1,2]，和预期结果完全一致。

内容的提问来源于stack exchange，提问作者Crade47