產生數字的所有排列組合

Question

有一個數列為 1,2,3,4
如何用C語言 有效率的產生所有的排列組合呢？
並且將數列一一列印出來
例如:
1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
.............
.............
共 4! = 24種 排列組合方法

Answer 1

摘自 排列組合 。。。 說明
將一組數字、字母或符號進行排列，以得到不同的組合順序，例如1 2 3這三個數的排列組合有：1 2 3、1 3 2、2 1 3、2 3 1、3
1 2、3 2 1。

解法
可以使用遞迴將問題切割為較小的單元進行排列組合，例如1 2 3 4的排列可以分為1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4
[1 2 3]進行排列，這邊利用旋轉法，先將旋轉間隔設為0，將最右邊的數字旋轉至最左邊，並逐步增加旋轉的間隔，例如：

1 2 3 4 -> 旋轉1 -> 繼續將右邊2 3 4進行遞迴處理
2 1 3 4 -> 旋轉1 2 變為 2 1-> 繼續將右邊1 3 4進行遞迴處理
3 1 2 4 -> 旋轉1 2 3變為 3 1 2 -> 繼續將右邊1 2 4進行遞迴處理
4 1 2 3 -> 旋轉1 2 3 4變為4 1 2 3 -> 繼續將右邊1 2 3進行遞迴處理

實作
C

#include #include #define N 4 void perm(int*, int); int main(void) { int num[N+1], i; for(i = 1; i <= N; i++) num[i] = i; perm(num, 1); return 0; } void perm(int* num, int i) { int j, k, tmp; if(i < N) { for(j = i; j <= N; j++) { tmp = num[j]; // 旋轉該區段最右邊數字至最左邊 for(k = j; k > i; k--) num[k] = num[k-1]; num[i] = tmp; perm(num, i+1); // 還原 for(k = i; k < j; k++) num[k] = num[k+1]; num[j] = tmp; } } else { // 顯示此次排列 for(j = 1; j <= N; j++) printf("%d ", num[j]); printf("\n"); } } 對於常見的程式演算。。。可以參考我的筆記：常見程式演算。。。