Java使用ArrayList实现nextPermutation下一个排列算法问题求助

• 查找j的起始位置错误：算法要求从序列最右端（索引为currentPermutation.size() - 1）开始查找第一个大于currentPermutation.get(i)的元素，你现有代码从currentPermutation.size() - 2开始遍历，会漏掉最后一个元素，导致找到的j不符合要求。
• 查找j的终止位置错误：你现有代码遍历j到索引0为止，实际上我们只需要在i的右侧（索引大于i的范围）查找即可，不需要遍历i左侧的元素，会做无效遍历甚至逻辑错误。
• 缺少最大排列的重置逻辑：如果从右往左遍历完所有i都没有找到符合currentPermutation.get(i+1) > currentPermutation.get(i)的位置，说明当前是最大排列，你现有代码没有执行Collections.sort(currentPermutation)的重置操作，不符合需求。
• 缺少小长度序列的边界判断：如果序列长度小于2时，不存在下一个排列，直接返回原序列即可，虽然现有代码不会报错，但加显式判断逻辑更清晰。

实现步骤 #

1. 特殊情况判断：如果序列长度小于2，直接返回当前序列
2. 从右向左遍历找第一个位置i，满足currentPermutation.get(i) < currentPermutation.get(i+1)
3. 如果未找到i（i < 0），说明当前为最大排列，执行Collections.sort(currentPermutation)重置后返回
4. 找到i后，从序列最右端开始向左遍历，找第一个位置j，满足currentPermutation.get(j) > currentPermutation.get(i)
5. 交换i和j位置的元素
6. 反转i+1到序列末尾的所有元素，得到下一个排列
7. 返回修改后的序列

完整代码 #

import java.util.ArrayList;
import java.util.Collections;

// 假设currentPermutation是当前类的成员变量，以下是方法实现
public ArrayList<Integer> nextPermutation() {
    int n = currentPermutation.size();
    // 长度小于2直接返回
    if (n < 2) {
        return currentPermutation;
    }
    
    // 找第一个i满足nums[i] < nums[i+1]
    int i = n - 2;
    while (i >= 0 && currentPermutation.get(i) >= currentPermutation.get(i + 1)) {
        i--;
    }
    
    // 未找到i，是最大排列，重置为升序
    if (i < 0) {
        Collections.sort(currentPermutation);
        return currentPermutation;
    }
    
    // 从右端找第一个大于nums[i]的j
    int j = n - 1;
    while (currentPermutation.get(j) <= currentPermutation.get(i)) {
        j--;
    }
    
    // 交换i和j位置元素
    Collections.swap(currentPermutation, i, j);
    
    // 反转i右侧的元素，保证升序
    Collections.reverse(currentPermutation.subList(i + 1, n));
    
    return currentPermutation;
}

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