排列算法分析及實現(C/OC)

排列簡介

一般地，從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列，叫做從n個元素中取出m個元素的一個排列(Sequence,Arrangement, Permutation)。 根據排列的定義，兩個排列相同，當且僅當兩個排列的元素完全相同，且元素的排列順序也相同。例如，abc與abd的元素不完全相同，它們是不同的排列；又如abc與acb，雖然元素完全相同，但元素的排列順序不同，它們也是不同的排列。

例如1 2 3這三個數的排列組合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。

排列算法分析

可以使用遞歸將問題切割為較小的單元進行排列組合，例如12 3 4的排列可以分為1[2 3 4]、2 [1 34]、3 [1 24]、4 [1 23]進行排列，這邊利用旋轉法，先將旋轉間隔設為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/OC）

#define N 5//數組元素個數

//主程序
int num[N+1];//排列時，有用下標從1開始
for(int tp = 1; tp <= N; tp++)
    num[tp] = tp;//數組中第tp個數大小為tp
perm(num, 1);//進行排列組合

//對num進行排列組合，從第i個開始
void perm(int* num, int i) {//num為被排列的數組，大小不變，其中元素順序在變化；i為要排列的第幾個數字
    int j, k, tmp;
    if(i < N) {//遞歸繼續的條件，i==N時，最後一個數字不用排列了，故輸出結果
        for(j = i; j <= N; j++) {//j從要排列的數字開始
            tmp = num[j];//臨時保存
            for(k = j; k > i; k--)//循環，進行第i個位置的排列，可以填第i及第i個後面的任何一個數字
                num[k] = num[k-1];
            num[i] = tmp;//給最左邊的位置賦值，i有值了，遞歸i+1
            perm(num, i+1);
            
            for(k = i; k < j; k++)//還原，因為父循環要進行第i個的排列（i後面有好幾個數字的話，每個數字都要排一次）
                num[k] = num[k+1];//還原
            num[j] = tmp;//還原，給最右邊的位置賦值
        }
    }
    else {  //一次遞歸結束，顯示此次排列
        for(j = 1; j <= N; j++)
            printf("%d ", num[j]);
        printf("\n");
    }
}