排列組合

在PTT看到[問題] 關於排列組合，就是印出集合的所有排列組合3的字的集合印出{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

• 最簡單的：用迴圈
  

  #include <iostream>
  using namespace std;void main() {
      char a[]="ABC";
      int i,j,k,n;
      n = strlen(a);
      for (i=0;i<n;i++) {
          for (j=0;j<n;j++) {
              for (k=0;k<n;k++) {
                  if (a[i]!=a[j] && a[i]!=a[k] && a[j]!=a[k])
                      cout << a[i] << a[j] << a[k] << endl;
              }
          }
      }
  }

  
  
• 再來是用stack+迴圈
  

  #define MAX 5
  
  int mark[MAX+1]= {0};// 記錄某一元素是否已使用
  int stack[MAX+1]; // 記錄放進去的先後
  // mark[0]、stack[0] 不放資料
  
  run=1; // 記錄是不是還要找下去
  
  len=0; // 目前的長度
  while(run) {
      if(len<MAX) {
          從 mark[] 中找到第一個還沒放進去的為 k
          mark[k]=1;
          stack[++len]=k;
      }
      else // len==MAX
      {
          從 stack[1] 到 stack[MAX] 全部印出來
          從 stack[MAX] 往前找到第一個非遞增的數為 k, 其位置為 j
          // 例如 3 4 5 2 1, 從後前找 1 2 5 是遞增, 但是 4 不是,
  
          // 所以 k=4, j=2
          如果找不到, 則把 run 設成 0, 並且 break;
          // 例如 5 4 3 2 1, 這是最後一種排列, 找完這一個就可以結束了
          把 stack[j] 到 stack[MAX] 的所有數對應 mark[] 值都設為 0,
          // 也就是把這些數拿出來
          再找 k 的下一個還沒放進去的數為 m
          len=j;
          stack[j]=m;
          mark[m]=1;
          // 例如 3 4 5 2 1, 則把 4 5 2 1 拿出來之後剩 3,
  
          // 再找 4 的下一個為 5 放進去, 就變成 3 5
      }
  }
  

  
  
• 用recursive的 良葛格的Algorithm Gossip
  

  #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");
      }
  }