n個有序的元素應有n!個不同的排列,如若一個排列使得所有的元素不在原來的位置上,則稱這個排列為錯排;有的叫重排。
如,1 2的錯排是唯一的,即2 1。1 2 3的錯排有31 2,2 3 1。這二者可以看作是1 2錯排,3分別與1、2換位而得的。
基本介紹
- 中文名:錯排問題
- 外文名:Derangement
基本信息
錯排公式
遞歸關係
通項公式求解
錯排生成算法
- 從右往左找下降,找到下降位置為pos;如果pos>Flag,則pos=Flag,並清空pos及其後所有位置的元素;
- 對該排列的第pos個元素,從原先的取值開始往上加。對於某一新的取值,如果滿足錯排,則將其記為pos的元素,設定i=pos,重置Flag=n+1並退出;否則,從該位置起重新進入1),即繼續往前找下降的位置。
- 前4個循環形成了2143,均滿足錯排規則;第5個循環中,只剩下數字5,不得不安排到第5個位置上,形成了21435,破壞了規則,Flag=5;
- 下一個循環i=6,Flag=5,進入紅色方框,下降的位置為4,小於Flag,所以pos取4,清空pos及其後位置上的3、5;pos位置從3開始往上加,加到5,滿足錯排,設定pos的元素為5,i=4,Flag=6;
- 下一個循環i=5,設定末尾元素為3,滿足規則,i=5,Flag=6;
- 下一個循環i=6,Flag=5+1表明滿足錯排,num++,輸出第一個錯排21453;然後按照字典序找到下一個排列21534,滿足錯排,Flag=6,設定i=5;
- 下一個循環i=6,Flag=5+1表明滿足錯排,num++,輸出第二個錯排21534;然後按照字典序找到下一個排列21543,不滿足錯排,記錄Flag=4,設定i=5;
- 下一個循環i=6,Flag=4,進入紅色方框,如上算法得到pos=2,設定pos的元素為3,i=2,Flag=6;
- 接下來三個循環設定末尾三位為1、5、4;i=5,Flag=6;
- ……
- 至少從不滿足錯排的位置和下降的位置兩者之左開始進行調整,從而跳過了不必要的循環。
- 設定關鍵位置的元素後,其後元素(除末尾)的設定依然按照錯排規則進行,因此也跳過了不滿足錯排的排列。
- 依然沿用了字典序法中找下一個排列的方法,用以快速尋找滿足錯排的下一個排列,越到最後,該排列越可能滿足錯排,所以採用了直接生成再判斷的方法,而沒有採用逐元判斷生成的方法。
性能分析
算法 | n=9 | n=10 | n=11 | n=12 | n=13 |
改進字典序法 | 5 | 44 | 468 | 5534 | 69704 |
文獻[2]方法 | 5 | 51 | 553 | 6552 | 83087 |
篩選法 | 8 | 84 | 1050 | 13553 | 181979 |
遞歸法 | 21 | 186 | 2067 | 25243 | 334661 |
原始碼
void Recursion(int x){ if (x > n) { num_r++; for (int i = 1; i <= n; i++)//輸出每一個錯排 printf("%d ",dearr_r[i]); printf("\n"); return; } for (int i = 1; i <= n; i++) { if (occup_r[i] == 0 && x != i) //x指安排第x個位置 { occup_r[i] = 1; //vis[i]記錄i是否已經被安排 dearr_r[x] = i; Recursion(x + 1); occup_r[i] = 0; //回退,撤銷安排的i } }}
int LexiOrder(int n){ int num_l = 0; bool Flag = true; int *seq = new int[n]; for (int i = 0; i < n; i++) seq[i] = i + 1; num_l++; for (int i = 0; i < n; i++) { if (seq[i] == i + 1) { num_l--; Flag = false; break; } } if (Flag) { for (int i = 0; i < n; i++)//輸出每一個錯排 printf("%d ",seq[i]); printf("\n"); } for (int i = n - 2; i >= 0;) { if (seq[i] < seq[i+1]) { for (int j = n - 1;j >= 0; j--) { if (seq[j] > seq[i]) { int tmp = seq[i]; seq[i] = seq[j]; seq[j] = tmp; for (int k1 = i + 1, k2 = n - 1; k1 < k2; k1++, k2--) { int tmp = seq[k1]; seq[k1] = seq[k2]; seq[k2] = tmp; } num_l++; Flag = true; for (int i = 0; i < n; i++) { if (seq[i] == i + 1) { num_l--; Flag = false; break; } } if (Flag) { for (int i = 0; i < n; i++)//輸出每一個錯排 printf("%d ",seq[i]); printf("\n"); } i = n - 2; //重新從右邊開始 break; } } } else i--; } delete []seq; return num_l;}
int AdLxOrder(int n){ int num_a = 0; int *dearr = new int[n + 1]; int *occup = new int[n + 1]; int Flag = n + 1; //記錄不滿足錯排的元素位置,均滿足則為n+1 for (int i = 0; i <= n; i++){ dearr[i] = 0;occup[i] = 0;} for (int i = 1, len = 0; i <= n + 1; i++) { if (i < n) //安排第i個位置 { for (int j = 1; j <= n; j++) //安排第i個位置 { if (occup[j] == 0 && j != i) { occup[j] = 1; //occup[j]記錄j是否已經被安排 dearr[i] = j; //安排dearr[i] break; } } } else if (i == n) //安排最後一位 { for (int j = 1; j <= n; j++) //安排第i個位置,無論是否滿足 { if (occup[j] == 0) { occup[j] = 1; //occup[j]記錄j是否已經被安排 dearr[i] = j; if (j == i) Flag = n; break; } } } else //i == n+1 { if (Flag == n + 1) //滿足,輸出,並找字典序下一個 { num_a++; for(int k = 1;k <= n; k++) printf("%d ",dearr[k]); printf("\n"); int pos = 0; for (int k = n; k > 1; k--) //從右往左找下降 { if (dearr[k - 1] < dearr[k]) { pos = k - 1; for (int m = n; m > pos; m--) { if (dearr[m] > dearr[pos]) //找到後綴中較大的最小元素 { if (dearr[m] == pos) Flag = pos; //記錄不滿足的位置 int tmp = dearr[m]; //交換 dearr[m] = dearr[pos]; dearr[pos] = tmp; //記錄不滿足的位置(只記錄最左側) for (int k1 = pos+1, k2 = n; k1 < k2; k1++, k2--) { if (dearr[k1] == k2 && Flag > k2) Flag = k2; //記錄不滿足的位置 if (dearr[k2] == k1 && Flag > k1) Flag = k1; //記錄不滿足的位置 int tmp = dearr[k2]; //陸續交換 dearr[k2] = dearr[k1]; dearr[k1] = tmp; } i = n; //循環末尾有i++,此處特取n break; } } break; } } } else //找關鍵位置的下一個值 { //關鍵位置:下降位置和不滿足位置的最左者 int pos = 0; for (int k = n; k > 1; k--) //從右往左找下降 { if (dearr[k - 1] < dearr[k]) { pos = k - 1; if (pos > Flag) //pos取下降位置和不滿足位置的最左者 pos = Flag; for (int m = pos; m <= n; m++) occup[dearr[m]] = 0; //全部重置 for (int m = dearr[pos] + 1; m <= n; m++) //從dearr[pos]+1開始找 { if (occup[m] == 0 && m != pos) //給pos找到下一個值 { dearr[pos] = m; occup[m] = 1; i = pos; Flag = n + 1; break; } } if (Flag == n + 1) break; else k = pos + 1; //重新向前找下降,循環末尾有k--,此處特+1 } } } } } delete []dearr; delete []occup; return num_a;}