Java中全排列的生成算法汇总

一、什么是全排列

全排列，是指将一组数按一定顺序进行排列，称为这组数的全排列。

如有三个数a、b、c，则它们的全排列有：a、b、c、ab、ac、ba、bc、ca、cb、abc、acb、bac、bca、cab、cba 共6个。

二、生成全排列的算法

在Java中，生成全排列的算法有以下几种：

1.递归算法

这种算法实现简单，思路清晰，需要定义一个交换方法以便在生成全排列的过程中进行交换。

示例代码如下：

public void recursionArrange(int[] array, int start, int end) {
    if (start == end) {
        // 输出一组排列
        System.out.println(Arrays.toString(array));
    } else {
        for (int i = start; i <= end; i++) {
            swap(array, start, i); //交换
            recursionArrange(array, start + 1, end); // 继续生成下一位
            swap(array, start, i); // 还原
        }
    }
}

public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

2.字典序法

这种算法也很容易理解，它是按照字典序的顺序生成全排列。

示例代码如下：

public void dictArrange(int[] array) {
    // 设置第一个排列
    Arrays.sort(array);
    System.out.println(Arrays.toString(array));
    while (true) {
        int i = array.length - 2;
        // 找到需要交换的位置i
        while (i >= 0 && array[i] >= array[i + 1]) {
            i--;
        }
        if (i < 0) {
            // 已最后一个排列
            break;
        }
        int j = array.length - 1;
        // 找到需要交换的位置j
        while (j >= 0 && array[j] <= array[i]) {
            j--;
        }
        swap(array, i, j); // 交换
        reverse(array, i + 1, array.length - 1); // 将交换后的位置后面的数字重新排序
        System.out.println(Arrays.toString(array)); // 输出新的排列
    }
}

public void reverse(int[] array, int start, int end) {
    while (start < end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}

public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

三、使用全排列的场景

全排列是一个非常有用的算法，它可以用于以下场景：

1. 计算一组数的所有组合情况；
2. 密码破解；
3. 数字游戏等。

四、结语

本文介绍了两种生成Java全排列的算法，并讲解了全排列的使用场景。根据具体的需求，可以灵活选择不同的算法。