转载

从基础讲全排列（Java实现）

提起全排列，第一印象是不是大学概率中的排列和组合呢，回头翻了翻书（怪自己太笨，记不住），才发现全排列是排列的一种。那就先延伸一下 排列 和 组合 呗。

排列

一般地说，从n个不同元素中，任取m(m≤n)个元素，按照一定的顺序排成一列，这就叫做从n个元素中取出m个元素的一个排列。

在排列数公式中，当 m=n

时，有：

这表明，n个不同元素全部取出来排列的排列数等于自然数1到n的 连乘积 。n个不同元素，全部取出的一个排列叫做n个不同元素的一个 全排列

。自然数1到n的连乘积叫做n的阶乘，用n!表示，所以n个不同元素的全排列公式则为：

例如：写出一个数组{a,b,c}的全排列。

对于初学者可以先画下图来算出：

共6个排列，这个数值6是可以根据乘法原理算出来的。第一次有3种选择,第二次有2种选择，第三次就有1种选择。据此共有N=3 X 2 X 1=6种。

先看两道题，旷视最近笔试考了这么一道题：

对于这道题你有思路吗？可以这样考虑：

a) 七人的全排列有A(7,7)=5040种排法，由于A，B是对等的，也就是说A在B的左边和B在A的左边的
站法数量是相同的，所以有A（7,7）/2=2520种；
b)把AB当成一个整体，求全排列，就是6! = 720
复制代码

算法实现

public static void perm(int A[], int p, int q){
		if(p == q){
		    // 输出所有结果
			printAll(A, q+1);
		}else{
			int i;
			for(i=p; i<=q; i++){
			    // 交换
				swap(A, p, i);
				perm(A, p+1, q);
				swap(A, p, i);
			}
		}
	}
}
复制代码