From Gossip@caterpillar

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

Java

public class Permutation {
    public static void perm(int[] num, int i) {

        if(i < num.length - 1) { 
            for(int j = i; j <= num.length - 1; j++) { 
                int tmp = num[j]; 
                // 旋轉該區段最右邊數字至最左邊 
                for(int k = j; k > i; k--) 
                    num[k] = num[k-1]; 
                num[i] = tmp; 

                perm(num, i+1); 

                // 還原 
                for(int k = i; k < j; k++) 
                    num[k] = num[k+1]; 
                num[j] = tmp; 
            } 
        } 
        else {  // 顯示此次排列 
            for(int j = 1; j <= num.length - 1; j++) 
                System.out.print(num[j] + " "); 
            System.out.println(); 
        } 
    }

    public static void main(String[] args) {
        int[] num = new int[4+1]; 

        for(int i = 1; i <= num.length - 1; i++) 
            num[i] = i; 

        perm(num, 1); 
    }
}