循環左右移全排列生成算法

循環左右移法結合了循環左移的循環區間思想和鄰位對換的數字方向性思想。在循環左右移全排列生成算法當中，也是要首先確定數字的方向性。數字的方向性決定了搜尋區間到底是左循環區間還是右循環區間。算法的算數複雜為O(n*n*n!)。

基本介紹

  • 中文名：循環左右移全排列生成算法
  • 外文名：Rotate left Right permutation generation algorithm
算法原理,算法步驟,算法性能分析,效果展示,代碼實現,

算法原理

循環左右移法結合了循環左移的循環區間思想和鄰位對換的數字方向性思想。在循環左右移全排列生成算法當中，也是要首先確定數字的方向性。數字的方向性決定了搜尋區間到底是左循環區間還是右循環區間。
首先要確定循環左移排列到中介數的映射，下面以1-9的排列為例，使用遞減進制法表示中位數。首先要確定每一個數字的方向性，從2開始。同時，設定b2b3b4b5b6b7b8b9為我們要求的中介數。對於每一個小於9的數i，如果i為奇數，其方向性決定於bi-1的奇偶性，奇向右、偶向左。如果i為偶數，其方向性決定於i-1+bi-2的奇偶性，同樣是奇向右、偶向左（當i=2時，方向一定向左）。確定方向性後，就要構造一個以i開始，以i+1為結束的循環區間，此循環區間的方向是背向i的方向。在此區間裡比i小的數字個數就是bi的值。但到計算b9時是沒法構造循環空間的，b9的值就是背向9的方向到排列數字邊界之間比9小的數字的個數（在此退化為鄰位對換法）
對於從中介數到原排列的映射，當我們知道了b2b3b4b5b6b7b8b9，自然而然就可以得到每個數字的方向性，具體規則同上。我們先畫9個空格，以從9到2的填充順序依次計算他們的位置。數格的方向除了9是從排列邊界沿著9的方向之外，其它的數字都是以上一個數字開始，沿著此數字的方向對未占用空格的格數進行循環計數，最後剩下的一個空格上填入1即得到原排列。

算法步驟

設[a1,a2 ... aN]，我們使用遞減進位制數表示中介數。從0到N!枚舉中介數，對於每箇中介數將其翻譯成對應的排列，對於中介數最右邊的數x9，首先確定其方向，從空格的最右端起數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
4
2
3
1
1
4
2
3
3
1
4
2
2
3
1
4
3
1
2
4
1
2
4
3
2
4
3
1
4
3
1
2
4
3
2
1
1
4
3
2
2
1
4
3
3
2
1
4
1
3
2
4
3
2
4
1
2
4
1
3
4
1
3
2
4
2
1
3
3
4
2
1
1
3
4
2
2
1
3
4

代碼實現

void Rotate_Left_Right(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));
int start, change;
if ((n % 2 == 1 && dec_num[n - 2] % 2 == 0) || (n % 2 == 0 && (dec_num[n - 2] + dec_num[n - 3]) % 2 == 0)) {
a[n - 1 - dec_num[n - 1]] = n;
vis[n - 1 - dec_num[n - 1]] = 1;
start = n - 1 - dec_num[n - 1];
}
else {
a[dec_num[n - 1]] = n;
vis[dec_num[n - 1]] = 1;
start = dec_num[n - 1];
}
for (int j = n - 2; j > 0; j--){
if (j == 1){
change = -1;
}
else if (((j + 1) % 2 == 1 && dec_num[j - 1] % 2 == 0) || ((j + 1) % 2 == 0 && (dec_num[j - 1] + dec_num[j - 2]) % 2 == 0)) {
change = -1;
}
else change = 1;
int count = dec_num[j] + 1;
while (count){
start += change;
if (start == -1) start = n - 1;
if (start == n) start = 0;
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 9:" << len << endl;
}

相關詞條

熱門詞條

聯絡我們