C++經典演算法題-排列組合

• 2020 年 2 月 13 日
• 筆記

27.Algorithm Gossip: 排列組合

說明

將一組數字、字母或符號進行排列，以得到不同的組合順序，例如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進行遞迴處理

程式碼示例

#include <stdio.h>  #include <stdlib.h>  #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");          }      }