全排列生成算法
此條目包含指南或教學內容。 (2017年6月20日) |
全排列的生成算法[1]方法是將給定的序列中所有可能的全排列無重複無遺漏地枚舉出來。此處全排列的定義是：從n個元素中取出m個元素進行排列，當n=m時這個排列被稱為全排列。
字典序、鄰位對換法、循環左移法、循環右移法、遞增進位製法、遞減進位製法都是常見的全排列生成算法。
字典序法
字典序，就是將元素按照字典的順序（a-z, 1-9）進行排列。以字典的順序作為比較的依據，可以比較出兩個串的大小。比如 "1" < "13"<"14"<"153"， 就是按每個數字位逐個比較的結果。對於一個串「123456789」， 可以知道最小的串是「123456789」，而最大的串「987654321」。這樣針對這個串以字典序法生成全排列生成全排列，就是依次生成「123456789」->「123456798」->......->"987654312"->"987654321"這樣的串。字典序法要求這一個與下一個有儘可能長的共同前綴，也即變化限制在儘可能短的後綴上。[2]
算法步驟
設P是集合{1，2，……n-1，n}的一個全排列：P=P1 P2……Pj-1 Pj Pj+1……Pn（1≤P1，P2，……，Pn≤n-1）
- 從排列的右端開始，找出第一個比右邊數字小的數字的序號 j，即 j=max{i|Pi<Pi+1，i>j}
- 在 Pj 的右邊的數字中，找出所有比Pj大的數字中最小的數字 Pk，即 k=min{i|Pi>Pj，i>j}
- 交換 Pj，Pk
- 再將排列右端的遞減部分 Pj+1 Pj+2……Pn倒轉，因為j右端的數字是降序，所以只需要其左邊和右邊的交換，直到中間，因此可以得到一個新的排列 P'=P1 P2……Pj-1 Pk Pn……Pj+2 Pj+1。
算法正確性證明
證明它可以生成所有的排列只需要證明生成的下一個排序恰好比當前排列大的一個序列即可。對於任意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階排列。[3]
鄰位對換法
該算法由Johnson-Trotter首先提出，是一個能快速生成全排列的算法。它的下一個全排列總是上一個全排列對換某相鄰兩位得到的。
算法步驟
- 初始化n個元素的排列為123……n，並規定其元素的方向都是向左的，元素的方向用一個數組b來表示，當b[i]=0，表示第i個元素的方向向左，當b[i]=1時表示第i個元素的方向向右。
- 在排列中找出排列中所有處於活動狀態的元素中最大的一個。
- 將它與它所指向相鄰元素交換。
- 把排列中大於上面找出的處在活動狀態的最大元素大的其他元素的方向倒轉。
算法正確性證明
假設其對n個元素能生成全排列，只需要證明其對n+1個元素，也能生成全排列，對於新進來的元素，將其認為值最大，插入最右方，每次從右移到左，或者改變方向後從左移到右就可以認為對於一個排列從不同位置插入生成一個新的排列，而對於n個元素是全排列的，因此對於n+1個元素也是全排列的，因此鄰位對換法能生成全排列。
遞增進位製法
這個算法是基於序列的遞增進位制數[3]。遞增進位制數是指數字的進制隨着位數的遞增而遞增。一般情況下，數字最右邊的進制是2，次右邊的進制是3，以此類推。n位遞增進位制數一共包含n!個數字，所以它可以與全排列生成算法結合在一起。
算法步驟
由於在字典序法中由中介數求排列比較繁瑣，可以通過另外定義遞增進位制數加以改進。定義: i的右邊比i小的數字的個數, 則()↑為遞增進位製法中定義的中介數，這裏的中介數是遞增進位制數字。例如，839647521對應的中介數為(67342221) ↑。由中介數求排列時，從大到小根據求出n,n-1,…,2,1的位置——從右向左將第+1個空填上i，剩下的最後一個空位填上1。因此根據「原排列」→「原中介數」→「新中介數」→」新排列「，在這樣的定義下，可以求出下一個排列。所以根據遞增進位製法生成全排列步驟如下：
- 初始化中介數（每一位都為0）
- 根據中介數求出對應的排列，輸出排列
- 如果沒有輸出所有的排列——中介數+1（這裏是遞增進位制數字的加法，區別於一般的十進制加法），跳回步驟（2）
如果已經輸出所有的排列——結束
算法正確性證明
對於一個給定的中介數，對應於一個唯一的排列，這裏排列和中介數的一一對應性的證明我們不做討論。m位(m為正整數)遞增遞減進位制數字有(m+1)！個，因此對於一個m位的中介數可能的取值有(m+1)！。又因為中介數與排列一一對應，所以由m位的中介數可以求出(m+1)！個排列。一個m位的中介數對應m+1個數字，m+1個不同元素的全排列有(m+1)！個。因此遞增進位製法可以生成全排列。
遞減進位製法
該方法與遞增進位製法的原理相似，不同的是它定義的「遞減進位制數」是數字的進制隨着位數的遞增而遞減。這種進制一般最左邊的進制是2，次左邊的進制是3。其餘原理與遞增進位製法基本相同。
算法步驟
在遞增進位制數法中，中介數的最低位是逢2進1，進位頻繁，這是一個缺點。把遞增進位制數翻轉,就得到遞減進位制數。遞減進位制數字是指數字的進制隨着數字位置的不同遞減。[3]
定義: i的右邊比i小的數字的個數, 則() ↓為遞減進位製法中定義的中介數，這裏的中介數是遞減進位制數字，遞減進位制數（a2 a3 a4 a5 a6 a7 a8 a9）為：最低位逢9進1，次低位逢8進1……。例如，839647521對應的中介數為(12224376)↓。由中介數求排列時，從大到小根據從大到小求出n,n-1,…,2,1的位置——從右向左將第+1個空填上i，剩下的最後一個空位填上1。因此根據「原排列」→「原中介數」→「新中介數」→」新排列「，在這樣的定義下，可以求出下一個排列。所以根據遞減進位製法生成全排列步驟如下：
- 初始化中介數（每一位都為0）
- 根據中介數求出對應的排列，輸出排列
- 如果沒有輸出所有的排列——中介數+1（這裏是遞減進位制數字的加法，區別於一般的十進制加法和遞增進位制數字加法），跳回步驟(2)
- 如果已經輸出所有的排列——結束
算法正確性證明
對於一個給定的中介數，對應於一個唯一的排列，這裏排列和中介數的一一對應性的證明我們不做討論。m位(m為正整數)遞減遞減進位制數字有(m+1)！個，因此對於一個m位的中介數可能的取值有(m+1)！。又因為中介數與排列一一對應，所以由m位的中介數可以求出(m+1)！個排列。一個m位的中介數對應m+1個數字，m+1個不同元素的全排列有(m+1)！個。因此遞減進位製法可以生成全排列。
實例：給定一個排列求後面或者前面的某個排列
由「原排列」→「原中介數」→「新中介數」→「新排列」的方式求解：
按照以上字典序法、遞增進位制數、遞減進位制數法和鄰位對換法四種算法，分別求出 83674521 之前第 2015 個排列。
| 中介數 | 2015中介數 | 新中介數 | 新排序 | 備註 |
|---|---|---|---|---|
| 7244221 | 243321 | 7000300 | 81237456 | 字典序法 |
| 7442221 | 243321 | 7153300 | 86451273 | 遞增法 |
| 1222447 | 10567 | 1211450 | 37624518 | 遞減法 |
| 1012120 | 10567 | 1001121 | 48673251 | 鄰位對換 |