循環左移全排列生成算法是全排列生成算法的一種，與遞減進位全排列生成算法非常相似。所謂左循環搜尋法是指從起始數字開始向左搜尋，如果到了左邊界還沒有發現終止數字，則從右邊界開始繼續尋找，直到終止數字被發現。該算法的總算數複雜度為O(n*n*n!)。
基本介紹
- 中文名：循環左移全排列生成算法
- 外文名：Rotate Left permutation generation algorithm
算法原理,算法步驟,算法性能分析,效果展示,代碼實現,
算法原理
循環左移排列生成算法與遞減進位排列生成算法非常相似，同樣是在原始排列中找到比當前數字小的數字個數。只不過循環左移使用的是左循環搜尋法，而不是遞減進位法使用的右側搜尋。所謂左循環搜尋法是指從起始數字開始向左搜尋，如果到了左邊界還沒有發現終止數字，則從右邊界開始繼續尋找，直到終止數字被發現。
首先要確定循環左移排列到中介數的映射，就是要為每一個數字確定這樣一個區間。以9位數的排列為例，方法是以從9到2的順序依次產生中介數中的數字，中介數從右向左產生（即原排列的9產生的數字放到中介數右數第一位，8產生的數字放到中介數右數第二位，以此類推。這樣才能得到遞減進位制數）。對於9，產生的中介數字依然是9的右邊比9小的數字的個數。但是從8開始一直到2中的每一個數i，都是要做一個以i+1為開始數字，i為結束數字的左循環區間，並看這個左循環區間中比i小的數字的個數。依次類推，得到當前排列所對應的中介數。
對於從中介數到原排列的映射，從中介數的最右邊向左邊開始計數逐個計數。計數的方法是，對於中介數最右邊的數x9，從空格的最右端起數x9個空格，在第x9+1個空格上填上9。然後對於中介數的每一位xi，沿著左循環的方向數xi個未占用空格，在第xi+1個空格里填上i，即可完成還原。
算法步驟
設[a1,a2 ... aN]，我們使用遞減進位制數表示中介數。從0到N!枚舉中介數，對於每箇中介數將其翻譯成對應的排列，對於中介數最右邊的數x9，從空格的最右端起數x9個空格，在第x9+1個空格上填上9。然後對於中介數的每一位xi，沿著左循環的方向數xi個未占用空格，在第xi+1個空格里填上i，最後剩餘的一個空位填上1，即可完成從中介數到原排列的轉化。
算法性能分析
記要全排列的元素總數為n，全排列一共n!種排列。我們在枚舉每一個中介數時，易知中介數有n-1位，對於中介數的每一位，我們需要掃描當前的n位數，找到當前位的位置，因此總複雜度為O(n*n*n!)。
效果展示
下表展示的是該算法下4!的排列的生成順序。
1 | 2 | 3 | 4 |
2 | 3 | 4 | 1 |
3 | 4 | 1 | 2 |
4 | 1 | 2 | 3 |
2 | 3 | 1 | 4 |
3 | 1 | 4 | 2 |
1 | 4 | 2 | 3 |
4 | 2 | 3 | 1 |
3 | 1 | 2 | 4 |
1 | 2 | 4 | 3 |
2 | 4 | 3 | 1 |
4 | 3 | 1 | 2 |
2 | 1 | 3 | 4 |
1 | 3 | 4 | 2 |
3 | 4 | 2 | 1 |
4 | 2 | 1 | 3 |
1 | 3 | 2 | 4 |
3 | 2 | 4 | 1 |
2 | 4 | 1 | 3 |
4 | 1 | 3 | 2 |
3 | 2 | 1 | 4 |
2 | 1 | 4 | 3 |
1 | 4 | 3 | 2 |
4 | 3 | 2 | 1 |
2 | 1 | 3 | 4 |
代碼實現
void rotate_left(int *a, int n) {
long len=count_factorial(n);
int dec_num[100] = {0};
bool vis[100];
for (int i = 0; i < len; i++) {
//求當前排列
memset(vis, 0, sizeof(vis));
a[n - 1 - dec_num[n - 1]] = n;
vis[n - 1 - dec_num[n - 1]] = 1;
int start = n - 1 - dec_num[n - 1];
for (int j = n - 2; j > 0 ; j--) {
int count = dec_num[j] + 1;
while (count){
start--;
if (start == -1) start = n - 1;
if (vis[start] == 0) count--;
}
a[start] = j + 1;
vis[start] = 1;
}
for (int j = n - 1; j >= 0; j--){
if (!vis[j]) {
vis[j] = 1;
a[j] = 1;
break;
}
}
//輸出排列
permutation_print(a,n);
//求下一中介數
dec_num[n - 1]++;
for (int i = n - 1; i > 0; i--) {
if (dec_num[i] == i + 1) {
dec_num[i - 1]++;
dec_num[i] = 0;
}
else break;
}
}
cout << "Total 8:" << len << endl;
}
