Oct
28
输出N个元素的全排列的算法
其实这个算法不复杂，但网上有人问，我就写了出来，顺便也贴在这里。
1,假设现有N个元素，记为 A[0..N-1]
2,先构造一个辅助数组 B[0..N-1]，初始值是(0, 1, 2, 3, ......, N-1)，即每个元素值就是其下标。
3,建立一个指针p，用来指示当前操作的进度，初始值为N-1，表示指向B[N-1]。
4,对应当前的辅助数组B，可以输出A的一个全排列C[0..N-1]。排列规则如下：
4.1, C可以是链接表或数组。先将其清空，即没有元素。
4.2, 取A[0]，根据B[0]的值决定插入在C的位置。比如A[0]=0，所以插入在最前面（第0个位置）。
4.3, 对于后续的A[i]，i=1, 2, .., N-1，其插入C的顺序由B[i]决定。比如A[5]=2，则表示将A[5]插入到C的现有元素的第2个元素后面位置。
4.4, 完成所有的A[i]
4.5, 输出当前的C，即为一个全排列。
5, 将当前p指向的B元素自减1。以进行到下一进度，具体算法：
5.1, B[p]大于0，则B[p]自减1。同时B中下标大于p的元素的值全部回到其初始值（元素初始值等于其下标）。p重新赋值为N-1。进到步骤6；
5.2, 如果B[p]=0，则先p自减1。
5.3, 如果p小于0，则全部进度已经完成，到步骤7(算法结束)。如果p大于等于0，则回到5.1。
6，回到步骤4。
7, 结束。
比如，对于3个元素1,2,3的情况,相应的B和输出C的变化如下：
B, C
012, 123
011, 132
010, 312
002, 213
001, 231
000, 321
