使用递归的简单python解决方案。

def get_permutations(string):

    # base case
    if len(string) <= 1:
        return set([string])

    all_chars_except_last = string[:-1]
    last_char = string[-1]

    # recursive call: get all possible permutations for all chars except last
    permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)

    # put the last char in all possible positions for each of the above permutations
    permutations = set()
    for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
        for position in range(len(all_chars_except_last) + 1):
            permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
            permutations.add(permutation)

    return permutations

递归是不必要的，甚至你可以直接计算任何排列，这个解决方案使用泛型来排列任何数组。

这里有关于这个algorihtm的很好的信息。

对于c#开发人员来说，这里有更有用的实现。

public static void main(String[] args) {
    String word = "12345";

    Character[] array = ArrayUtils.toObject(word.toCharArray());
    long[] factorials = Permutation.getFactorials(array.length + 1);

    for (long i = 0; i < factorials[array.length]; i++) {
        Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
        printPermutation(permutation);
    }
}

private static void printPermutation(Character[] permutation) {
    for (int i = 0; i < permutation.length; i++) {
        System.out.print(permutation[i]);
    }
    System.out.println();
}

该算法计算每个排列的时间和空间复杂度为O(N)。

public class Permutation {
    public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
        int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
        T[] permutation = generatePermutation(array, sequence);

        return permutation;
    }

    public static <T> T[] generatePermutation(T[] array, int[] sequence) {
        T[] clone = array.clone();

        for (int i = 0; i < clone.length - 1; i++) {
            swap(clone, i, i + sequence[i]);
        }

        return clone;
    }

    private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
        int[] sequence = new int[size];

        for (int j = 0; j < sequence.length; j++) {
            long factorial = factorials[sequence.length - j];
            sequence[j] = (int) (permutationNumber / factorial);
            permutationNumber = (int) (permutationNumber % factorial);
        }

        return sequence;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static long[] getFactorials(int length) {
        long[] factorials = new long[length];
        long factor = 1;

        for (int i = 0; i < length; i++) {
            factor *= i <= 1 ? 1 : i;
            factorials[i] = factor;
        }

        return factorials;
    }
}

改进的代码相同

    static String permutationStr[];
    static int indexStr = 0;

    static int factorial (int i) {
        if (i == 1)
            return 1;
        else
            return i * factorial(i-1);
    }

    public static void permutation(String str) {
        char strArr[] = str.toLowerCase().toCharArray();
        java.util.Arrays.sort(strArr);

        int count = 1, dr = 1;
        for (int i = 0; i < strArr.length-1; i++){
            if ( strArr[i] == strArr[i+1]) {
                count++;
            } else {
                dr *= factorial(count);
                count = 1;
            }       
        }
        dr *= factorial(count);

        count = factorial(strArr.length) / dr;

        permutationStr = new String[count];

        permutation("", str);

        for (String oneStr : permutationStr){
            System.out.println(oneStr);
        }
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            for (int i = 0; i < indexStr; i++){
                if(permutationStr[i].equals(prefix))
                    return;
            }        
            permutationStr[indexStr++] = prefix;
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }
    }

使用Es6的字符串排列

使用reduce()方法

Const排列= STR => { If (str.length <= 2) 返回str.length === 2 ?[str, str[1] + str[0]]: [str]; 返回str .split (") .reduce ( (acc, letter, index) => acc.concat(排列(str。Slice (0, index) + str.slice(index + 1))。Map (val =>字母+ val))， ［］ ）; }; console.log(排列(STR));

//插入每个字符到数组列表中

static ArrayList al = new ArrayList();

private static void findPermutation (String str){
    for (int k = 0; k < str.length(); k++) {
        addOneChar(str.charAt(k));
    }
}

//insert one char into ArrayList
private static void addOneChar(char ch){
    String lastPerStr;
    String tempStr;
    ArrayList locAl = new ArrayList();
    for (int i = 0; i < al.size(); i ++ ){
        lastPerStr = al.get(i).toString();
        //System.out.println("lastPerStr: " + lastPerStr);
        for (int j = 0; j <= lastPerStr.length(); j++) {
            tempStr = lastPerStr.substring(0,j) + ch + 
                    lastPerStr.substring(j, lastPerStr.length());
            locAl.add(tempStr);
            //System.out.println("tempStr: " + tempStr);
        }
    }
    if(al.isEmpty()){
        al.add(ch);
    } else {
        al.clear();
        al = locAl;
    }
}

private static void printArrayList(ArrayList al){
    for (int i = 0; i < al.size(); i++) {
        System.out.print(al.get(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);
            }
        }