这就是我通过对排列和递归函数调用的基本理解所做的。虽然要花点时间，但都是独立完成的。

public class LexicographicPermutations {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s="abc";
    List<String>combinations=new ArrayList<String>();
    combinations=permutations(s);
    Collections.sort(combinations);
    System.out.println(combinations);
}

private static List<String> permutations(String s) {
    // TODO Auto-generated method stub
    List<String>combinations=new ArrayList<String>();
    if(s.length()==1){
        combinations.add(s);
    }
    else{
        for(int i=0;i<s.length();i++){
            List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
            for (String string : temp) {
                combinations.add(s.charAt(i)+string);
            }
        }
    }
    return combinations;
}}

生成输出为[abc, acb, bac, bca, cab, cba]。

它背后的基本逻辑是

对于每个字符，将其视为第一个字符，并找出剩余字符的组合。例[abc](abc的组合)->。

a->[bc](a x Combination of (bc))->{abc,acb} b->[ac](b x组合(ac))->{bac,bca} c->[ab](c x Combination of (ab))->{cab,cba}

然后递归地分别调用每个[bc]，[ac]和[ab]。

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

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')

作为Python生成器，带有现代类型提示:

from typing import Iterator


def permutations(string: str, prefix: str = '') -> Iterator[str]:
    if len(string) == 0:
        yield prefix
    for i, character in enumerate(string):
        yield from permutations(string[:i] + string[i + 1:], prefix + character)


for p in permutations('abcd'):
    print(p)

这是一个具有O(n!)时间复杂度的算法，具有纯递归和直观。

public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
    words obj = new words();

    String str="premandl";
    obj.getcombination(str, str.length()-1, "");
    System.out.println(arrlist);

}


public void getcombination(String str, int charIndex, String output) {

    if (str.length() == 0) {
        arrlist.add(output);
        return ;
    }

    if (charIndex == -1) {
        return ;
    }

    String character = str.toCharArray()[charIndex] + "";
    getcombination(str, --charIndex, output);

    String remaining = "";

    output = output + character;

    remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);

    getcombination(remaining, remaining.length() - 1, output);

}

}

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

public class StringPermutation {

// Function to print all the permutations of str
static void printPermutn(String str, String ans) {

    // If string is empty
    if (str.length() == 0) {
        System.out.print(ans + " ");
        return;
    }

    for (int i = 0; i < str.length(); i++) {

        // ith character of str
        char ch = str.charAt(i);

        // Rest of the string after excluding
        // the ith character
        String ros = str.substring(0, i) + str.substring(i + 1);

        // Recurvise call
        printPermutn(ros, ans + ch);
    }
}


public static void main(String[] args) {
    String s = "ABC";
    printPermutn(s, "");
}

}