排列組合

說明

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

解法

如果是1 2，將兩個旋轉就得到新組合2 1。如果是 1 2 3，想到得2開頭的新組合，可以從1 2 3將2拿到前頭得到2 1 3，想得到3開頭的新組合，可以將3拿到前頭，得到3開頭的3 1 2。

可以觀察到，從1 2 3得到2 1 3，其實就是將開頭的1 2旋轉，從1 2 3得到3 1 2，就是將1 2 3旋轉。如果這樣的旋轉可以得到新排列，那麼對於1 2 3、2 1 3、3 1 2的尾數列2 3、1 3、1 2也作相同旋轉處理，不就也可以得到尾數列的新排列。也就是：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

以上紅色部份表示對整個數列作旋轉處理，底線表示對尾數列作旋轉處理，也就是對尾數列進行相同動作，這在程式上就是遞迴處理。因此對於任意長度的符號數列排列組合時，可對傳入數列作旋轉處理，旋轉間隔一開始是0，逐步增加，對旋轉過後的每個數列之尾數列再作排列組合。例如對於 1 2 3 4：

1 2 3 4 -> 旋轉 1 為 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 Java Python Scala Ruby JavaScript Haskell

#include <stdio.h> 
#include <stdlib.h> 
#define N 4 

void perm(int*, int, void (*)(int*));
void rotate(int*, int, int);
void copy(int*, int*);
void print(int*);

int main(void) { 
    int num[N] = {1, 2, 3, 4};
    perm(num, 0, print); 
    return 0; 
} 

void perm(int* num, int i, void (*take)(int*)) { 
    if(i < N) { 
        int j;
        for(j = i; j < N; j++) {
            int to[N];
            copy(num, to);
            rotate(to, i, j);
            perm(to, i + 1, take); 
        } 
    } else { take(num); }
}  

void rotate(int* num, int i, int j) {
    int tmp = num[j]; 
    int k;
    for(k = j; k > i; k--) {
        num[k] = num[k - 1]; 
    }
    num[i] = tmp;
}

void copy(int* from, int* to) {
    int i;
    for(i = 0; i < N; i++) {
        to[i] = from[i];
    }
}

void print(int* num) {
    int i;
    for(i = 0; i < N; i++) {
        printf("%d ", num[i]); 
    }
    printf("\n"); 
}

Java

import java.util.*;

public class Permutation {
    public static <T> List<T> rotatedTo(int i, List<T> list) {
        List<T> rotated = new ArrayList<>();
        rotated.add(list.get(i));
        rotated.addAll(list.subList(0, i));
        rotated.addAll(list.subList(i + 1, list.size()));
        return rotated;
    }

    public static <T> List<List<T>> allRotated(List<T> list) {
        List<List<T>> allRotated = new ArrayList<>();
        for(int i = 0; i < list.size(); i++) {
            allRotated.add(rotatedTo(i, list));
        }
        return allRotated;
    }
            
    public static <T> List<List<T>> perm(List<T> list) {
        List<List<T>> pls = new ArrayList<>();
        
        if(list.isEmpty()) {
            pls.add(new ArrayList<T>());
        } else {
            for(List<T> lt : allRotated(list)) {
                for(List<T> tailPl : perm(lt.subList(1, lt.size()))) {
                    List<T> pl = new ArrayList<>();
                    pl.add(lt.get(0));
                    pl.addAll(tailPl);
                    pls.add(pl);
                }
            }
        }
        
        return pls;
    }
                  
    public static void main(String[] args) {
        for(List<Integer> pl : perm(Arrays.asList(1, 2, 3, 4))) {
            System.out.println(pl);
        }
    }
}

Python

from functools import reduce

def allRotated(list):
    def rotatedTo(i):
        return [list[i]] + list[0:i] + list[i + 1:]
    return [rotatedTo(i) for i in range(len(list))]
   
def perm(list):
    if list == []:
        return [[]]
    else:
        lts = allRotated(list)
        return reduce(lambda a, b: a + b, 
            [[[lt[0]] + pl for pl in perm(lt[1:])] for lt in lts])
   
for list in perm([1, 2, 3, 4]):
    print(list)

Scala

def allRotated[T](list: List[T]) = {
    def rotatedTo(i: Int) = {
        list(i) :: (list.take(i) ++ list.drop(i + 1))
    }
    (for(i <- 0 until list.size) yield rotatedTo(i)).toList
}


def perm[T](list: List[T]): List[List[T]] = {
    if(list.isEmpty) List(Nil)
    else {
        val lts = allRotated(list)
        (for(lt <- lts) yield 
            (for(pl <- perm(lt.tail)) yield lt.head :: pl)).reduce(_ ++ _)
    }
}

perm(List(1, 2, 3, 4)).foreach(println)

Ruby

def allRotated(list)
    rotatedTo = ->(i) {
        [list[i]] + list.take(i) + list.drop(i + 1)
    }
    
    (0...list.size).map {|i| rotatedTo.call(i)}
end
   
def perm(list)
    if list == []
        [[]]
    else
        lts = allRotated(list)
        lts.map {|lt| 
            perm(lt.drop(1)).map {|pl| [lt[0]] + pl}
        }.reduce(:+)
    end
end
   
perm([1, 2, 3, 4]).each do |list|
    printf("%s\n", list)
end

JavaScript

function allRotated(list) {
    function rotatedTo(i) {
        var rotated = [];
        rotated.push(list[i]);
        return rotated.concat(list.slice(0, i))
                      .concat(list.slice(i + 1, list.length));
    }

    var all = [];
    for(var i = 0; i < list.length; i++) {
        all.push(rotatedTo(i));
    }
    return all;
}

function perm(list) {
    var pls = [];
    if(list.length == 0) {
        pls.push([]);
    } else {
        allRotated(list).forEach(function(lt) {
            perm(lt.slice(1, lt.length)).forEach(function(tailPl) {
                var pl = [];
                pl.push(lt[0]);
                pls.push(pl.concat(tailPl));
            });
        });
    }
    return pls;
}

perm([1, 2, 3, 4]).forEach(function(lt) {
    print(lt);
});

Haskell

allRotated list = [rotatedTo i | i <- [0..(length list) - 1]]
    where rotatedTo i = (list !! i) : 
            ((take i list) ++ (drop (i + 1) list))

perm list =
    if list == [] then [[]]
    else
        let lts = allRotated list
        in foldl1 (++) [[head lt : pl | pl <- perm \$ tail lt] | lt <- lts]
        
main = sequence [print lt | lt <- perm [1, 2, 3, 4]]