全排列

组合数学术语

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

简介

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

公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

共3*2*1=6种。

方法

以下介绍全排列算法四种：

(A)字典序法

(B)递增进位制数法

(C)递减进位制数法

(D)邻位对换法

字典序法

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。

[例]字符集{1,2,3},较小的数字较先,

这样按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。

1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

[例]839647521是1--9的排列。

1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到987654321，也就没有下一个了。否则找出第一次出现下降的位置。

[序数公式]

有从 1 到 n 的连续的 n 个自然数，其全排列按照从小到大排列，次序从 0 到 n!-1 ，总共 n! 个。现有其全排列中的一组 “、、……”，其全排列次序为：

递增进位制数法

1)由排列求中介数在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。

在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，

右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。上面是由中介数求排列。

由序号（十进制数）求中介数（递增进位制数）如下：

m=m1,0≤m≤n!-1

m1=2m2+kn-1,0≤kn-1≤1

m2=3m3+kn-2,0≤kn-2≤2

……………

mn-2=(n-1)mn-1+k2,0≤k2≤n-2

mn-1=k1,0≤k1≤n-1

p1p2…pn←→(k1k2…kn-1)↑←→m

在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。

为方便起见，令ai+1=kn-1，i=1,2,…,n-1

(k1k2…kn-1)↑=(anan-1…a2)↑

ai：i的右边比i小的数字的个数

在这样的定义下，

有839647521←→(67342221)↑

(67342221)↑+1=(67342300)↑←→849617523

6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905

由(anan-1…a2)↑求p1p2…pn。

从大到小求出n,n-1,…,2,1的位置

_ ... _ n _ _ …_ (an个空格)

n的右边有an个空格。

n-1的右边有an-1个空格。

…………

2的右边有a2个空格。

最后一个空格就是1的位置。

递减进位制数法

在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。

把递增进位制数翻转,就得到递减进位制数。 (anan-1…a2)↑→(a2a3…an-1an)↓

839647521→ (12224376)↓

(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989

[注意]求下一个排列十分容易

邻位对换法

递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。

这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。

递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。这个算法可描述如下：

对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。

对1—n-1的每一个奇排列，n从左到右插入n个空档，生成1—n的n个排列。

对[2,n]的每个数字都是如此。

839647521

字典序法递增进位制法递减进位制法邻位对换法

下一个 839651247 849617523 893647521 836947521

中介数 72642321↑ 67342221↑ 12224376↓ 10121372↓

序号 297191 279905 340989 203393

生成树

生成树中介数

可以采用树的结构表示全排列生成算法，以数字的全排列生成算法为例，从最小的数1开始，其全排列只有一种可能；加入数字2，数字2可以插入在1的后边或前边，有两个不同位置；

再加入3，对于第二层中的每一种不同排列，都可以通过将3插入不同位置得到三种不同的排列数，共有6种排列数；一次类推可以得到个数的全排列。

基于此，可以构造一种新的中介数，其定义如下：

对于生成树中的第n层，每一个节点中介数的前n-2位继承于其父节点的中介数，中介数最后一位为该层新加入的数减去其右边相邻的数。

如果新加入的数在最右边，则中介数最后一位为0。

如图5所示，排列数12的中介数为0，对于生成树第三层由节点12扩展得到的新节点，当新加入的数3位于最右边时（即排列数123），对应的中介数为00；若3插入12中间，则中介数末位为3-2=1，即中介数为01；类似地排列数312对应的中介数为02。

不难看出，生成树中介数也是递减进位制数，但和递减进位制数法是不同的。如排列数231对应的生成树中介数为12，而递减进位制数法对应的中介数为11。

算法完备性

不难看出，全排列生成树每一层的不同节点对应的中介数都是不同的，这是因为：

（1）每个子节点中介数的前缀都从其父节点继承得到，因此不同父节点生成的子节点中介数一定不同；

（2）同一个父节点生成的子节点，父节点的排列数每一位都是不同的，因此新加入的数插入不同位置得到的中介数的最后一位一定是不同的。

由以上两点及归纳法即可证明生成树每一层不同节点对应的中介数都是唯一不重复的。又全排列生成树每一个节点的排列数是无重复无遗漏的，因此从中介数到排列数的映射是一一对应的，从而基于生成树中介数的全排列生成算法是完备的。

计算排列数

由生成树中介数还原排列数的过程实际上就是全排列生成树的构建过程。以生成树中介数121为例：

（1）中介数第一位是1，说明2在1的左边，得到21；

（2）中介数第二位为2，只能由3-1得到，说明3在1的左邻，得到231；

（3）中介数第三位为1，只能由4-3得到，说明4在3的左邻，得到2431.

对于任意的生成树中介数，都通过类似的过程计算对应的排列数。不难看出，从生成树中介数还原排列数的时间复杂度也是。

递归

设(ri)perm(X)表示每一个全排列前加上前缀ri得到的排列.当n=1时,perm(R)=(r) 其中r是唯一的元素,这个就是出口条件.

当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)构成.

函数Perm(int list[],int k,int m)是求将list的第0~k-1个元素作为前缀、第k~m个元素进行全排列得到的全排列，如果k为0，且m为n，就可以求得一个数组中所有元素的全排列。

其想法是将第k个元素与后面的每个元素进行交换，求出其全排列。这种算法比较节省空间。

非递归

n个数的排列可以从1.2....n开始,至n.n-1....2.1结束。

也就是按数值大小递增的顺序找出每一个排列。

以6个数的排列为例，其初始排列为123456,最后一个排列是654321,如果当前排列是124653,找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数，如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。

本例中将找到46,计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数，本例找到的数是5，其位置计为j，将i与j所在元素交换125643,然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列，如此下去，直至654321为止。算法结束。

Heap

#include

#define MAX 100

void process(char *c,int n){

int i = 0;

while(i < n){

i++;

}

void perm(char *list,int n){

int k;

char tmp;

int i = n;

int count[MAX];

count[i - 1] = 1;

while(i > 2){

i--;

count[i - 1] = 1;

}

process(list,n);

do{

if(count[i - 1] < i){

if(i % 2 != 0)

k = 1;

else

k = count[i - 1];

tmp = list[k - 1];

list[k - 1] = list[i - 1];

list[i - 1] = tmp;

count[i - 1] += 1;

i = 2;

process(list,n);

}else{

count[i - 1] = 1;

i += 1;

}

}while(i <= n);

}

int main(){

char c[] = {'a','b','c','d'};

perm(c,4);

}

Java

Pascal

C++实现

字典序法

JavaScript/AS3/TS

先取数据长度决定换多少次相邻位，每一次邻位对换之后的结果其实就是新的不会有相同的组合

并行加速

由于全排列生成中包含大量规则一致的映射和运算操作，因而可以利用并行计算的方法对全排列的生成算法进行加速，这里提出了一种基于GPU并行计算的加速框架，可以与现有全排列生成算法整合，以实现全排列生成的加速。具体而言，针对全排列算法本身支持的不同操作，有如下三种情况：

中介数映射

若全排列生成算法只支持中介数→排列的映射，那么我们可以提出如下的加速框架：

考虑全排列算法A，其支持的操作为：先按照一定规则R产生中介数I，接着基于某种映射算法根据每个中介数I计算出其对应的全排列P。这样，在遍历了所有n!个中介数后，便可以产生所有的全排列。

可以看出，其并行部分主要体现在从中介数I映射产生排列P的过程上，因而，可以采用如下的算法框架：

1、产生包含所有中介数的集合S

2、将S分割成为m个子集，其中m为GPU核数。

3、对于并行计算的每个核，其独立计算每个子集Si中所有中介数→排列的映射。

4、合并所有核的计算结果。

可以看出，在理想的情况下，该算法框架的加速比应为m。

随机递推

一般而言，生成所有全排列时，递推算法的效率要高于中介数→排列的映射。因而，对于支持递推操作的全排列生成算法，可以提出更优化的框架。另一方面我们可以看到，某些全排列生成算法只支持递推操作而不存在对应的中介数，所以，对于这类算法，我们的加速框架应如下修改：

考虑全排列算法A，其支持的操作为：先产生原始排列P0，接着基于某种递推算法，根据当前得到的排列产生下一个排列，计算序列为P0→P1→P2……→Pn。这样，在遍历了所有n!个排列后，便可以产生所有的全排列。

可以看出，每个单独的递推过程是互不干扰的。因而，我们可以通过产生多个递推的种子，通过多核同时递推的方式来对递推进行加速。但是，由于我们对算法的细节并没有更多的认识，所以初始种子的产生并没有可以依赖的规则。在实践中，可以采用随机的方法，随机产生m个种子。其对应的算法框架如下：

1、随机产生m个初始排列，其中m为GPU核数。

2、对于并行计算的每个核，其独立根据初始排列中的一个进行递推，直到其抵达了某个已经产生过的排列为止。

3、合并所有核的计算结果。

这里需要注意的是，在该算法框架下，每个核的任务量很可能是不平均的。每次递推产生一个新排列，都需要检查是否已经出现过。若没有出现过，则可以继续递推，否则意味着这个核的任务结束。在实践中，可以通过一个长度为n!的bool数组来记录每个排列的出现情况，通过hash算法来实现O(1)时间的查找。实践证明，其效果是稳定、有效的。

并行递推

对于同时支持中介数和递推方法的全排列生成算法，我们可以同时利用中介数的有序性和递推算法的高效性，从而设计出更加高效的加速框架。具体而言，我们可以改进随机递推方法，通过中介数的引用来使得各个核的任务量平均分配，从而实现全局效率的最优化。

考虑全排列算法A，其支持两种操作：1、基于某个已有的排列P1，递推出其下一个排列P2。2、基于某个中介数I，通过映射产生出其对应的排列P。这样，在进行了足够的映射和递推操作后，便可以产生所有的全排列。

与随机递推方法类似，可以看出，每个单独的递推过程是互不干扰的。不同之处在于，中介数的引入使得全排列的集合S成为一个全序集，从而我们可以迅速得到某个位置的排列。因而，我们可以通过计算和中介数映射使得每个递推的种子均匀分布在集合中，保证每个核的工作量相同，从而避免多核中的木桶短板效应，实现效率的全局最优化。具体而言，其对应的算法框架如下：

1、对每个核，计算出其对应种子中介数的编号1，n!/m,2*n!/m,……这些编号均匀分布在1~n!上。

2、根据这些编号分别产生出每个核对应种子的中介数。

3、对于每个核，根据其中介数得到其递推的种子排列。

4、每个核同时进行递推操作，直到递推了n!/m次为止。

5、合并所有核的计算结果。

可以看到，相比于随机递推方法，中介数的引入带来了很大的优势。首先，全排列与中介数的一一映射关系使得全排列集合成为全序集，从而可以保证每个核的运算量是相等的，避免了并行计算中任务分配不均匀带来的短板效应。另一方面，每个核的任务均匀意味着可以提前知道每个核需要进行的递推次数，从而避免了每一次递推后都需要查看是否已经出现过的时间开销，大大提升了效率。实践证明，并行递推的算法加速比是最高的。

完备性

由于所有全排列算法必须至少支持中介数映射或递推操作中的一种，因而上面的加速框架可以适应所有的全排列生成算法，为其提供并行加速功能。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省