# 排列組合

## 解法

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

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

## 實作：CJavaPythonScalaRubyJavaScriptHaskell

• C
``#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 reducedef 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(:+)    endend   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]]``