nextPermutation标准写法

生成下一个全排列

public boolean nextPermutation(int[] num) {
    if (num.length <= 1) return false;
    // 从后往前选择数字，直到找到一个数字的连续两位是升序的
    // 这个时候从最后开始遍历,找到一个元素大于前面选择的数字
    // 交换这两个元素
    // 并对第一个元素之后的所有元素排序
    for (int i = num.length - 2; i >= 0; i--) {
        if (num[i] < num[i + 1]) {
            int j;
            for (j = num.length - 1; j >= i; j--) {
                if (num[i] < num[j]) break;
            }
            // swap the two numbers.
            num[i] = num[i] ^ num[j];
            num[j] = num[i] ^ num[j];
            num[i] = num[i] ^ num[j];
            //sort the rest of arrays after the swap point.
            Arrays.sort(num, i + 1, num.length);
            return true;
        }
    }
    // 如果遍历到最后都不是逆序的了,将当前的数组逆序,并返回false
    
    //reverse the arrays.
    for (int i = 0; i < num.length / 2; i++) {
        int tmp = num[i];
        num[i] = num[num.length - i - 1];
        num[num.length - i - 1] = tmp;
    }
    return false;
}

原始版本链接

public void nextPermutation(int[] num) {
    if (num.length <= 1)
        return;
    for (int i = num.length - 2; i >= 0; i--) {
        if (num[i] < num[i + 1]) {
            int j;
            for (j = num.length - 1; j >= i; j--)
                if (num[i] < num[j])
                    break;
            // swap the two numbers.  
            num[i] = num[i] ^ num[j];
            num[j] = num[i] ^ num[j];
            num[i] = num[i] ^ num[j];
            //sort the rest of arrays after the swap point.  
            Arrays.sort(num, i + 1, num.length);
            return;
        }
    }
    //reverse the arrays.  
    for (int i = 0; i < num.length / 2; i++) {
        int tmp = num[i];
        num[i] = num[num.length - i - 1];
        num[num.length - i - 1] = tmp;
    }
    return;
}

参考文献

java有自带类似于c++里面的next_permutation函数吗?_百度知道 (baidu.com)

赏

谢谢你请我吃糖果

微信