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

这里有关于这个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;
    }
}

python实现

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')

如果有人想要生成排列来做一些事情，而不是通过void方法打印它们:

static List<int[]> permutations(int n) {

    class Perm {
        private final List<int[]> permutations = new ArrayList<>();

        private void perm(int[] array, int step) {
            if (step == 1) permutations.add(array.clone());
            else for (int i = 0; i < step; i++) {
                perm(array, step - 1);
                int j = (step % 2 == 0) ? i : 0;
                swap(array, step - 1, j);
            }
        }

        private void swap(int[] array, int i, int j) {
            int buffer = array[i];
            array[i] = array[j];
            array[j] = buffer;
        }

    }

    int[] nVector  = new int[n];
    for (int i = 0; i < n; i++) nVector [i] = i;

    Perm perm = new Perm();
    perm.perm(nVector, n);
    return perm.permutations;

}

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

示例:取输入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
    }
}

这个没有递归

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;
}

简单的递归c++实现如下所示:

#include <iostream>

void generatePermutations(std::string &sequence, int index){
    if(index == sequence.size()){
        std::cout << sequence << "\n";
    } else{
        generatePermutations(sequence, index + 1);
        for(int i = index + 1 ; i < sequence.size() ; ++i){
            std::swap(sequence[index], sequence[i]);
            generatePermutations(sequence, index + 1);
            std::swap(sequence[index], sequence[i]);            
        }
    }
}

int main(int argc, char const *argv[])
{
    std::string str = "abc";
    generatePermutations(str, 0);
    return 0;
}

输出:

abc
acb
bac
bca
cba
cab

更新

如果想要存储结果，可以将vector作为函数调用的第三个参数传递。此外，如果您只想要唯一的排列，您可以使用集合。

#include <iostream>
#include <vector>
#include <set>

void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){
    if(index == sequence.size()){
        //std::cout << sequence << "\n";
        v.push_back(sequence);
    } else{
        generatePermutations(sequence, index + 1, v);
        for(int i = index + 1 ; i < sequence.size() ; ++i){
            std::swap(sequence[index], sequence[i]);
            generatePermutations(sequence, index + 1, v);
            std::swap(sequence[index], sequence[i]);            
        }
    }
}

int main(int argc, char const *argv[])
{
    std::string str = "112";
    std::vector <std::string> permutations;
    generatePermutations(str, 0, permutations);
    std::cout << "Number of permutations " << permutations.size() << "\n";
    for(const std::string &s : permutations){
        std::cout << s << "\n";
    }
    std::set <std::string> uniquePermutations(permutations.begin(), permutations.end());
    std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n";
    for(const std::string &s : uniquePermutations){
        std::cout << s << "\n";
    }
    return 0;
}

输出:

Number of permutations 6
112
121
112
121
211
211
Number of unique permutations 3
112
121
211