递归实现全排列

全排列的定义

从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(" ");
    }
}