STJ全排列生成算法

SJT算法，即Steinhaus–Johnson–Trotter algorithm，是一種全排列生成算法。在該算法中，不斷的尋找一種相鄰元素相互交換的順序，根據這種交換的順序，依次計算下一個排列。該算法的算數複雜度是O(n*n!)。

基本介紹

• 中文名：STJ全排列生成算法
• 外文名：Steinhaus–Johnson–Trotter algorithm
• 學科：計算機科學

算法原理

SJT算法，即Steinhaus–Johnson–Trotter algorithm，是一種全排列生成算法。在該算法中，不斷的尋找一種相鄰元素相互交換的順序，根據這種交換的順序，依次計算下一個排列。在SJT算法中，每次循環都進行一次滿足條件的相鄰元素的交換，直到不存在滿足條件的可交換的元素，此時說明所有排列的情況均已輸出，算法結束。

算法步驟

設[a1,a2 ... aN] 每一項都有向左或向右兩個移動方向。

1) 初始化所有移動方向向左；

2) 如果移動方向的值比自己小，就可移動，比如 <1 >2 <3, 每個數字前箭頭的方向表示該數字的移動方向，3可以移動，2和1不可移動；

3) 移動最大的可以動項，在上面例子中就是數字3；

4) 將所有比移動項大的項方向反轉，重複第三步，直到不能移動為止。

算法性能分析

記要全排列的元素總數為n，全排列一共n!種排列，在每次枚舉下一個排列時，我們都在上一個排列中尋找最大的可移動項，然後對其進行移動，因此總體複雜度是O(n*n!)。

代碼實現

void SJT(int *a, int n){long len=count_factorial(n);int b[100] = {0};int direction[100];for (int i = 0; i < n; i++) direction[i] = -1;int pos = n - 1;for (int i = 0; i < len; i++){permutation_print(a, n);if (direction[pos] == -1 && pos > 0){int next_pos = direction[pos] + pos;swap(a[pos], a[next_pos]);swap(direction[pos], direction[next_pos]);pos = next_pos;}else if (direction[pos] == 1 && pos < n - 1){int next_pos = direction[pos] + pos;swap(a[pos], a[next_pos]);swap(direction[pos], direction[next_pos]);pos = next_pos;}else{int max_pos = -1, max_num = -1;for (int j = 0; j < n; j++){int next_pos = j + direction[j];if (next_pos < 0 || next_pos >= n) continue;if (a[next_pos] > a[j]) continue;if (max_pos == -1 || a[max_pos] < a[j]){max_pos = j;max_num = a[max_pos];}}if (max_pos == -1) break;int next_pos = max_pos + direction[max_pos];swap(a[max_pos], a[next_pos]);swap(direction[max_pos], direction[next_pos]);for (int j = 0; j < n; j++){if (a[j] > max_num) direction[j] = -direction[j];}}}cout<<"Total 6:"<<len<<endl;}