我一直在学习递归思考，第一个打动我的自然解决方案如下。一个更简单的问题是找到一个短一个字母的字符串的排列。我将假设，并相信我的每一根纤维，我的函数可以正确地找到一个字符串的排列，比我目前正在尝试的字符串短一个字母。

Given a string say 'abc', break it into a subproblem of finding permutations of a string one character less which is 'bc'. Once we have permutations of 'bc' we need to know how to combine it with 'a' to get the permutations for 'abc'. This is the core of recursion. Use the solution of a subproblem to solve the current problem. By observation, we can see that inserting 'a' in all the positions of each of the permutations of 'bc' which are 'bc' and 'cb' will give us all the permutations of 'abc'. We have to insert 'a' between adjacent letters and at the front and end of each permutation. For example

我们有bc

“a”+“bc”=“abc”

“b”+“a”+“c”=“bac”

“b”+“a”=“b”

对于'cb'我们有

a + b = acb

“c”+“a”+“b”=“cab”

“cb”+“a”=“cb”

下面的代码片段将说明这一点。下面是该代码片段的工作链接。

def main():
    result = []
    for permutation in ['bc', 'cb']:
        for i in range(len(permutation) + 1):
            result.append(permutation[:i] + 'a' + permutation[i:])
    return result


if __name__ == '__main__':
    print(main())

完整的递归解将是。下面是完整代码的工作链接。

def permutations(s):
    if len(s) == 1 or len(s) == 0:
        return s
    _permutations = []
    for permutation in permutations(s[1:]):
        for i in range(len(permutation) + 1):
            _permutations.append(permutation[:i] + s[0] + permutation[i:])
    return _permutations


def main(s):
    print(permutations(s))


if __name__ == '__main__':
    main('abc')

//循环'整个字符数组，并保持'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);
        }
    }
}

没有递归的Java实现

public Set<String> permutate(String s){
    Queue<String> permutations = new LinkedList<String>();
    Set<String> v = new HashSet<String>();
    permutations.add(s);

    while(permutations.size()!=0){
        String str = permutations.poll();
        if(!v.contains(str)){
            v.add(str);
            for(int i = 0;i<str.length();i++){
                String c = String.valueOf(str.charAt(i));
                permutations.add(str.substring(i+1) + c +  str.substring(0,i));
            }
        }
    }
    return v;
}

递归Python解决方案

def permute(input_str):
    _permute("", input_str)

def _permute(prefix, str_to_permute):
    if str_to_permute == '':
        print(prefix)

    else:
        for i in range(len(str_to_permute)): 
            _permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])

if __name__ == '__main__':
    permute('foobar')

改进的代码相同

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

这里有一个优雅的，非递归的O(n!)解:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }