让我试着用Kotlin来解决这个问题:

fun <T> List<T>.permutations(): List<List<T>> {
    //escape case
    if (this.isEmpty()) return emptyList()

    if (this.size == 1) return listOf(this)

    if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))

    //recursive case
    return this.flatMap { lastItem ->
        this.minus(lastItem).permutations().map { it.plus(lastItem) }
    }
}

核心概念:将长链表分解成小链表+递归

长答案与示例列表[1,2,3,4]:

即使是一个4种组合的列表，在脑海中列出所有可能的排列已经有点令人困惑了，我们需要做的就是避免这种情况。我们很容易理解如何对大小为0、1和2的列表进行排列，因此我们所需要做的就是将它们分解为这些大小中的任何一个，并将它们正确地组合起来。想象一台头奖机器:这个算法将从右向左旋转，然后写下

当列表大小为0或1时，返回空/列表为1 当列表大小为2时处理(例如[3,4])，并生成2个排列([3,4]& [4,3]) 对于每一项，将其标记为最后一项中的最后一项，并找到列表中其余项目的所有排列。(例如，把[4]放在桌子上，把[1,2,3]重新排列) 现在对它的子元素进行所有的排列，把它自己放回列表的末尾(例如:[1,2,3][，4]，[1,3,2][，4]，[2,3,1][，4]，…)

让我们以输入abc为例。

从集合(["c"])中的最后一个元素(c)开始，然后将最后第二个元素(b)添加到它的前面，末尾和中间的每个可能位置，使其["bc"， "cb"]，然后以同样的方式将后面的下一个元素(a)添加到集合中的每个字符串中，使其:

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"] 

因此整个排列:

["abc", "bac", "bca","acb" ,"cab", "cba"]

代码:

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

我的实现基于Mark Byers上面的描述:

    static Set<String> permutations(String str){
        if (str.isEmpty()){
            return Collections.singleton(str);
        }else{
            Set <String> set = new HashSet<>();
            for (int i=0; i<str.length(); i++)
                for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
                    set.add(str.charAt(i) + s);
            return set;
        }
    }

简单的解决方案，利用swift语言的特点，数组是值类型。

func permutation(chrs: [String], arr: [String], result: inout [[String]]) {
   if arr.count == chrs.count {
       result.append(arr)
       return
   }

   for chr in chrs {
       var arr = arr
       if !arr.contains(chr) {
           arr.append(chr)
           permutation(chrs: chrs, arr: arr, result: &result)
       }
   }
}

func test() {
   var result = [[String]]()
   let chrs = ["a", "b", "c", "d"]
   permutation(chrs: chrs, arr: [], result: &result)
}

复杂度O(n * n!)

//循环'整个字符数组，并保持'i'作为你的排列的基础，并像你交换[ab, ba]一样继续寻找组合

public class Permutation {
    //Act as a queue
    private List<Character> list;
    //To remove the duplicates
    private Set<String> set = new HashSet<String>();

    public Permutation(String s) {
        list = new LinkedList<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            list.add(s.charAt(i));
        }
    }

    public List<String> getStack(Character c, List<Character> list) {
        LinkedList<String> stack = new LinkedList<String>();
        stack.add(""+c);
        for(Character ch: list) {
            stack.add(""+ch);
        }

        return stack;
    }

    public String printCombination(String s1, String s2) {
        //S1 will be a single character
        StringBuilder sb = new StringBuilder();
        String[] strArr = s2.split(",");
        for(String s: strArr) {
            sb.append(s).append(s1);
            sb.append(",");
        }       
        for(String s: strArr) {
            sb.append(s1).append(s);
            sb.append(",");
        }

        return sb.toString();
    }

    public void printPerumtation() {
        int cnt = list.size();

        for(int i = 0; i < cnt; i++) {
            Character c = list.get(0);
            list.remove(0);
            List<String> stack = getStack(c, list);

            while(stack.size() > 1) {
                //Remove the top two elements
                String s2 = stack.remove(stack.size() - 1);
                String s1 = stack.remove(stack.size() - 1);
                String comS = printCombination(s1, s2);
                stack.add(comS);
            }

            String[] perms = (stack.remove(0)).split(",");
            for(String perm: perms) {
                set.add(perm);
            }

            list.add(c);
        }

        for(String s: set) {
            System.out.println(s);
        }
    }
}

import java.io.*;
public class Anagram {

public static void main(String[] args) {
      java.util.Scanner sc=new java.util.Scanner(System.in);
            PrintWriter p=new PrintWriter(System.out,true);
            p.println("Enter Word");
            String a[],s="",st;boolean flag=true;
            int in[],n,nf=1,i,j=0,k,m=0;
            char l[];
            st=sc.next();
            p.println("Anagrams");
            p.println("1 . "+st);
            l=st.toCharArray();
            n=st.length();
            for(i=1;i<=n;i++){
                nf*=i;
            }

            i=1;
            a=new String[nf];
            in=new int[n];
            a[0]=st;
            while(i<nf){
                for(m=0;m<n;m++){
                    in[m]=n;
                }j=0;
                while(j<n){
                    k=(int)(n*Math.random());

                    for(m=0;m<=j;m++){
                        if(k==in[m]){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        in[j++]=k;
                    }flag=true;
                }s="";
                for(j=0;j<n;j++){
                    s+=l[in[j]];
                }

                //Removing same words
                for(m=0;m<=i;m++){
                        if(s.equalsIgnoreCase(a[m])){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        a[i++]=s;
                        p.println(i+" . "+a[i-1]);
                    }flag=true;

            }

    }
}