全排列的定义
从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(" ");
}
}