对上述过程，一般地，对于i，将前一步所得的每 一排列重复 i 次，然后将 i 由第一排的最后往前移， 至最前列，正好走了 i 次,下一个接着将 i 放在下一 排列的最前面，然后依次往后移，一直下去即得 i 元排列。 下面我们用较正式的语言来说这件事。
对给定的一个整数k，我们赋其一个方向，即在其 上写一个箭头（指向左侧或右侧）
1.2 排列组合生成算法
1. 全排列的生成算法 2. 组合的生成算法
3. 一般排列的生成算法
1. 全排列的生成算法
全排列的生成算法就是对于给定的字符集，用有 效的方法将所有可能的全排列无重复无遗漏地枚 举出来。
这里介绍4种全排列算法： (A) 直接生成法 (B) 序数法 (C) 字典序法 (D) 换位法
n的p进制表示： n a i p i , 0 a i p
i 1
i 1 k
我们来看另一种表示
n!=((n-1)+1)(n-1)!=(n-1)(n-1)!+(n-1)!, (n-1)!=(n-2)(n-2)!+(n-2)!, …, 故 n!= (n-1)(n-1)!+ (n-2)(n-2)!+…+2×2!+2!
3. 一般排列的生成算法
n中取r的排列生成可以由组合生成和全排列生成 结合而得到。
839647521的下一个为839651247。
一般而言，设P是[1,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
(1) 找出 j=max{ i |Pi<Pi+1}，k=max{ i |Pi>Pj}； (2) 对换 Pj，Pk； (3) 将 Pj+1…Pk-1PjPk+1…Pn翻转， P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一个。 该算法的优点是排列清晰，而且保持着字典序。 缺点是算法较繁琐。
k 或者 k
考虑{1,2…n}的一个排列，其上每一个整数都给了一 个方向。 我们称整数k是可移的(Mobile&Active)，如果它的 箭头所指的方向的邻点小于它本身。
例如 263154 中6、3、5都是可移的。
显然1永远不可移； n除了以下两种情形外，它都是可移的： (1) n是第一个数，且其方向指向左侧，
…………….
m n 2 ( n 1) m n 1 a n 2 , m n 1 a n 1 , 0 a n 1 n 1
( a n 1 , a n 2 ,..., a 2 , a1 ) m
下面我们试图将n-1个元素的序列(an-1,…,a1)与n个元 素的排列建立起一一对应关系。 序列(an-1,…,a1)与某一排列p=p1p2…pn之间的对应关 系为： ai 表示排列p中的数i+1所在位置的右边比它小的数 的个数。
即 n ! 1
k k!
k 1
n 1
不难证明，从0到n!-1的任何数m可唯一的表示为
m a n 1 ( n 1)! a n 2 ( n 2)! ... a1 1!
其中
0 a i i , i 1,..., n 1.
所以从0到n!-1的n!个整数与
(an-1,an-2,…a2,a1)
一一对应。
从m计算出an-1,an-2,…a2,a1的算法如下：
m m1 , 0 m n ! 1 0 a1 1 0 a2 2 0 a n2 n 2 m 1 2 m 2 a1 , m 2 3 m3 a2 ,
例如：839647521是1-9的一个排列，求出下一个。 (1-9的排列最前面的是123456789，最后面的是 987654321，从右向左扫描若都是增的，就到了 987654321，也就没有下一个了。) (1) 从右向左扫描找出第一次出现下降的位置。(4) (2) 在4的右边按从左往右的顺序找出最后一个比4 大的数字(5)，交换这两个数字，得到839657421。 (3) 把5后面的数字顺序完全颠倒过来即得到：
例如：p=4213 (a3,a2,a1)= (301)
反过来, 由(a3,a2,a1)= (301)也可以得到排列4213，
由a3=3, 知4放在空格的最左端,
4 2 1 3 _ _ _ _
而a2=0,说明3的右边没有比它更小的，故3放在最 右端， 考虑a1=1,容易得出，2右边还有一个空格放1，于是 得到了排列4213。 这个算法的优点是建立了自然序数和排列之间的一 一对应关系(通过n-1个元素的序列(an-1,…,a1) )。 缺点是这种对应关系需要通过序列转换，即两层对 应关系，多一层计算量。
(2) n是最后一个数，且其方向指向右侧。
于是，我们可由 12......n 按如下算法产生所有排列：
1、开始时：12......n
2、当存在可移数时，
(a) 找最大的可移数m； (b) 将m与其箭头所指的邻数互换位置； (c) 将所得排列中比m大的数p的方向调整，即改 为相反方向。
(A) 直接生成法
递推算法：
假设已经生成n-1个数的所有(n-1)!个全排列， 将n插入到每一个排列的前面、第12之间、第23 之间、。。。 最后，即得到n个数的所有n(n-1)!=n! 个全排列。 优点是生成简便，缺点是速度慢。
(B) 序数法
i n的十进制表示： n a i 10 , 0 a i 10 k
2. 组合的生成算法
设从[1,n]中取r元的一个组合为C1C2…Cr， 不妨设C1＜…＜Cr ,则 i≤Ci≤(n-r+i), i=1,2,…,r。 生成C1C2…Cr的下一个组合的算法如下： (1) 找 j = max{ i |Ci＜n-r+i}； (2) 令 Cj = Cj+1； (3) 令 Ci = Ci-1+1, i=j+1,…,r。 这等于给所有的组合建立了字典序。
1 2 3 13 2 31 2 32 1 2 31 2 1 3
第四步： 1 2 3 4 1 2 4 3 1 4 2 3 41 2 3 3 2 41 1 4 3 2 1 34 2 1 3 2 4 3 1 2 4 3 1 4 2 3 4 1 2 43 1 2
43 2 1 3 42 1 3 24 1 3 2 14 2 3 14 2 34 1 243 1 42 3 1 42 1 3 241 3 2 143 2 1 34
1 2 34 1 24 3 1 4 2 3 4 1 2 3 4 1 3 2 1 4 3 2 1 34 2 1 3 24 3 1 24 3 14 2 3 4 1 2 4 3 1 2
4 3
3 3 3 2 2 2 42 42 2 2 2
2 1 42 1 2 41 2 1 4 3 1 4 3 41 43 1 3 1 1 3 41 3 1 43 1 3 4
(C) 字典序法
字典序：对于两个序列a1…ak和b1…bk ，若存在t， 使得ai=bi, i<t，但at<bt ，则称
a1 ... a k b1 ... bk
例如对于字符集{1,2,3}，较小的数字较先，这样按 字典序生成的全排列是：123,132,213,231,312,321
一个全排列可看做一个字符串，字符串可有前缀、 后缀。关键是如何生成给定全排列的下一个排列。 所谓一个的下一个就是这一个与下一个之间没有其 他的。这就要求这一个与下一个有尽可能长的共同 前缀，也即变化限制在尽可能短的后缀上。
(D) 换位法
基于直接生成法，[n]的全排列可由[n-1]的全排 列生成： 给定[n-1]的一个排列,将n 由最右端依次插入排 列п，即得到n个[n]的排列： p1 p2…pn-1n p1 p2…npn-1
…
np1 p2…pn-1
例如对于 n=4 第一步： 第二步： 第三步： 1 1 2 2 1
