递归实现全排列

全排列的定义

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

公式

全排列数f(n)=n!(定义0!=1)

思路

解决一个算法问题，先思考我们自己是如何写一组数的全排列的：1，2，3，4，5
12345（第一个）
首先保持第一个不变，对2345进行全排列。
同样地，我们先保持2不变，对345进行全排列。
保持3不变，对45对进行全排列，保持4不变，对5进行全排列.
由于5只有一个，它的排列只有一种：5。
故先对12进行全排列

12345 12354 12435 12453 12543 12534

对13进行全排列

13245 13254 13425 13452 13542 13524

… …
依次类推，则实现了1为前缀的全排列。接着以2，3，4，5为前缀进行排列。
附代码实现

package part2;


/** * @create 2019-09-20 10:23 */
public class FullPermutation {
   
    private static char[] text = {
   '1', '2', '3', '4', '5'};

    public static void main(String[] args) {
   
        System.out.println("{1, 2, 3, 4, 5}的全排列为：");
        permutation(text, 0, text.length);
        System.exit(0);
    }

    /** * 全排列输出 * * @param a 要输出的字符数组 * @param startIndex 输出字符数组的起始位置 * @param length 输出字符数组的长度 */
    private static void permutation(char[] a, int startIndex, int length) {
   
        int i;
        char t;
        if (startIndex < length - 1) {
   
            permutation(a, startIndex + 1, length);
            for (i = startIndex + 1; i < length; i++) {
   
                t = a[startIndex];
                a[startIndex] = a[i];
                a[i] = t;
                permutation(a, startIndex + 1, length);
                t = a[startIndex];
                a[startIndex] = a[i];
                a[i] = t;
            }
        } else {
   
            printResult(a);
        }
    }

    /** * 输出指定字符数组 * * @param text 将要输出的字符数组 */
    private static void printResult(char[] text) {
   
        for (char c : text) {
   
            System.out.print(c);
        }
        System.out.print(" ");
    }
}