简单的解决方案，利用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!)

这个没有递归

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}

这对我很有效。

import java.util.Arrays;

public class StringPermutations{
    public static void main(String args[]) {
        String inputString = "ABC";
        permute(inputString.toCharArray(), 0, inputString.length()-1);
    }

    public static void permute(char[] ary, int startIndex, int endIndex) {
        if(startIndex == endIndex){
            System.out.println(String.valueOf(ary));
        }else{
            for(int i=startIndex;i<=endIndex;i++) {
                 swap(ary, startIndex, i );
                 permute(ary, startIndex+1, endIndex);
                 swap(ary, startIndex, i );
            }
        }
    }

    public static void swap(char[] ary, int x, int y) {
        char temp = ary[x];
        ary[x] = ary[y];
        ary[y] = temp;
    }
}

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1，因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }

我们可以用阶乘来计算有多少字符串以某个字母开头。

示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}

下面是两个c#版本(仅供参考): 1. 打印所有排列 2. 返回所有排列

算法的基本要点是(可能下面的代码更直观-尽管如此，下面的代码是做什么的一些解释): -从当前索引到集合的其余部分，交换当前索引处的元素 -递归地获得下一个索引中剩余元素的排列 -恢复秩序，通过重新交换

注意:上述递归函数将从起始索引中调用。

private void PrintAllPermutations(int[] a, int index, ref int count)
        {
            if (index == (a.Length - 1))
            {
                count++;
                var s = string.Format("{0}: {1}", count, string.Join(",", a));
                Debug.WriteLine(s);
            }
            for (int i = index; i < a.Length; i++)
            {
                Utilities.swap(ref a[i], ref a[index]);
                this.PrintAllPermutations(a, index + 1, ref count);
                Utilities.swap(ref a[i], ref a[index]);
            }
        }
        private int PrintAllPermutations(int[] a)
        {
            a.ThrowIfNull("a");
            int count = 0;
            this.PrintAllPermutations(a, index:0, count: ref count);
            return count;
        }

版本2(与上面相同-但返回排列而不是打印)

private int[][] GetAllPermutations(int[] a, int index)
        {
            List<int[]> permutations = new List<int[]>();
            if (index == (a.Length - 1))
            {
                permutations.Add(a.ToArray());
            }

            for (int i = index; i < a.Length; i++)
            {
                Utilities.swap(ref a[i], ref a[index]);
                var r = this.GetAllPermutations(a, index + 1);
                permutations.AddRange(r);
                Utilities.swap(ref a[i], ref a[index]);
            }
            return permutations.ToArray();
        }
        private int[][] GetAllPermutations(int[] p)
        {
            p.ThrowIfNull("p");
            return this.GetAllPermutations(p, 0);
        }

单元测试

[TestMethod]
        public void PermutationsTests()
        {
            List<int> input = new List<int>();
            int[] output = { 0, 1, 2, 6, 24, 120 };
            for (int i = 0; i <= 5; i++)
            {
                if (i != 0)
                {
                    input.Add(i);
                }
                Debug.WriteLine("================PrintAllPermutations===================");
                int count = this.PrintAllPermutations(input.ToArray());
                Assert.IsTrue(count == output[i]);
                Debug.WriteLine("=====================GetAllPermutations=================");
                var r = this.GetAllPermutations(input.ToArray());
                Assert.IsTrue(count == r.Length);
                for (int j = 1; j <= r.Length;j++ )
                {
                    string s = string.Format("{0}: {1}", j,
                        string.Join(",", r[j - 1]));
                    Debug.WriteLine(s);
                }
                Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count);
            }
        }