全排列生成算法

字典序法

字典序，就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据，可以比较出两个串的大小。比如 "1" < "13"<"14"<"153"， 就是按每个数字位逐个比较的结果。对于一个串“123456789”， 可以知道最小的串是“123456789”，而最大的串“987654321”。这样针对这个串以字典序法生成全排列生成全排列，就是依次生成“123456789”->“123456798”->......->"987654312"->"987654321"这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

算法正确性证明

证明它可以生成所有的排列只需要证明生成的下一个排序恰好比当前排列大的一个序列即可。对于任意j，作为从右端开始第一个小于右边数字的数，可以得到序列Pj+1，...Pn是降序排列，选择其中大于Pj的最小的数字Pk，与其交换，然后再对后面排序得到序列P1，...Pj-1Pk...Pn，恰好比P1...Pj-1Pj...Pn大一点的下一个排列，因此算法可以生成全排列。

例子

对于元素集合{1，2，3}按字典序生成的全排列是:123,132,213,231,312,321。
   // array必须是从小到大排好序的boolean dictSeq(int[] array) {
       // 从最右端开始第一个比右边小的位置int j = -1;
       for (int i=array.length-2; i>=0; i--) {
           if (array[i] < array[i+1]) {
               j = i;
               break;
           }
       }
       // 此时已经是最大序了if (j == -1) {
           System.out.println("end");
           return false;
       }
       // j后边比j位置大的最小的一个位置int k = -1;
       int min = Integer.MAX_VALUE;
       for (int i=j; i<array.length; i++) {
           if (array[i] > array[j] && array[i] <= min) { // 这里要找到最后一个，否则对于存在相同元素的集合会出现错误。如：0122
               min = array[i];
               k = i;
           }
       }
       // 交换j和k的值int tmp = array[j];
       array[j] = array[k];
       array[k] = tmp;
       // 对j后边的序列进行反转int left = j+1;
       int right = array.length - 1;
       while (left < right) {
           int t = array[left];
           array[left] = array[right];
           array[right] = t;
           left ++;
           right --;
       }
       for (int i : array) {
           System.out.print(i + ", ");
       }
       System.out.println();
       return true;
   }

插入法

如果已知n-1个元素的排列，将n插入到排列的不同位置，就得到了n个元素的排列。用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点：为了产生n个元素的排列，我们必须知道并存储所有n-1个元素的排列，然后才能产生出所有n阶排列。

邻位对换法

该算法由Johnson-Trotter首先提出，是一个能快速生成全排列的算法。它的下一个全排列总是上一个全排列对换某相邻两位得到的。

算法正确性证明

假设其对n个元素能生成全排列，只需要证明其对n+1个元素，也能生成全排列，对于新进来的元素，将其认为值最大，插入最右方，每次从右移到左，或者改变方向后从左移到右就可以认为对于一个排列从不同位置插入生成一个新的排列，而对于n个元素是全排列的，因此对于n+1个元素也是全排列的，因此邻位对换法能生成全排列。

递增进位制法

这个算法是基于序列的递增进位制数。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下，数字最右边的进制是2，次右边的进制是3，以此类推。n位递增进位制数一共包含n!个数字，所以它可以与全排列生成算法结合在一起。

算法正确性证明

对于一个给定的中介数，对应于一个唯一的排列，这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递增递减进位制数字有(m+1)！个，因此对于一个m位的中介数可能的取值有(m+1)！。又因为中介数与排列一一对应，所以由m位的中介数可以求出(m+1)！个排列。一个m位的中介数对应m+1个数字，m+1个不同元素的全排列有(m+1)！个。因此递增进位制法可以生成全排列。

递减进位制法

该方法与递增进位制法的原理相似，不同的是它定义的“递减进位制数”是数字的进制随着位数的递增而递减。这种进制一般最左边的进制是2，次左边的进制是3。其余原理与递增进位制法基本相同。

算法正确性证明

对于一个给定的中介数，对应于一个唯一的排列，这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递减递减进位制数字有(m+1)！个，因此对于一个m位的中介数可能的取值有(m+1)！。又因为中介数与排列一一对应，所以由m位的中介数可以求出(m+1)！个排列。一个m位的中介数对应m+1个数字，m+1个不同元素的全排列有(m+1)！个。因此递减进位制法可以生成全排列。