让我试着用kotlin解决这个问题：

fun <T> List<T>.permutations(): List<List<T>> {
    //escape case
    if (this.isEmpty()) return emptyList()

    if (this.size == 1) return listOf(this)

    if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))

    //recursive case
    return this.flatMap { lastItem ->
        this.minus(lastItem).permutations().map { it.plus(lastItem) }
    }
}

核心概念：将长列表分解为更小的列表+递归
用示例列表[1,2,3,4]给出长答案：
即使是一个4个的列表，试图列出你头脑中所有可能的排列也已经有点让人困惑了，我们需要做的就是避免这种情况。我们很容易理解如何对大小为0、1和2的列表进行所有排列，因此我们所需要做的就是将它们分解为这些大小中的任何一个，并将它们正确地组合起来。想象一台jackpot机器：该算法将从右向左旋转，然后写下
当列表大小为0或1时返回空/1的列表
当列表大小为2（例如[3,4]）时处理，并生成2个置换（[3,4]&[4,3]）
对于每个项目，将其标记为“最后一项”中的“最后一项”，并在列表中查找该项目其余部分的所有排列(e、 g.将[4]放在table上，并再次将[1,2,3]放入排列中）
现在所有的排列都是它的子项，把它自己放回列表的末尾（例如：[1,2,3][，4]，[1,3,2][，4]，[2,3,1][，4]，…）

这对我很有用。。

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

这就是我通过对置换和递归函数调用的基本理解所做的。需要一点时间，但这是独立完成的。

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

它生成的输出为 [, acb, bac, bca, cab, cba] .
其背后的基本逻辑是
对于每个字符，将其视为第一个字符并找到剩余字符的组合。例如 [](Combination of )-> . a->[bc](a x Combination of (bc))->{,acb} b->[ac](b x Combination of (ac))->{bac,bca} c->[ab](c x Combination of (ab))->{cab,cba} 然后递归地调用每个 [bc] , [ac] & [ab] 独立地。

使用递归。
当输入为空字符串时，唯一的排列是空字符串。请将字符串中的每个字母作为第一个字母进行尝试，然后使用递归调用查找其余字母的所有排列。

import java.util.ArrayList;
import java.util.List;

class Permutation {
    private static List<String> permutation(String prefix, String str) {
        List<String> permutations = new ArrayList<>();
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
            }
        }
        return permutations;
    }

    public static void main(String[] args) {
        List<String> perms = permutation("", "abcd");

        String[] array = new String[perms.size()];
        for (int i = 0; i < perms.size(); i++) {
            array[i] = perms.get(i);
        }

        int x = array.length;

        for (final String anArray : array) {
            System.out.println(anArray);
        }
    }
}

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

其中一个简单的解决方案就是使用两个指针递归地交换字符。

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}

这是一个优雅的、非递归的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;
    }

这个没有递归

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

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

（通过java编程介绍）

让我们使用输入 `` 举个例子。
从最后一个元素开始( c )一组( ["c"] )，然后添加最后一个元素( b 到它的前端，末端和中间的每一个可能的位置，使它 ["bc", "cb"] 然后以同样的方式从后面添加下一个元素( a )对集合中的每个字符串执行以下操作：

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"]

因此，整个排列：

["abc", "bac", "bca","acb" ,"cab", "cba"]

代码：

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

以前的所有贡献者都在解释和提供代码方面做得很好。我想我也应该分享这种方法，因为它可能也会帮助别人。该解决方案基于（heaps算法）
两件事：
请注意，excel中描述的最后一项只是为了帮助您更好地可视化逻辑。因此，最后一列中的实际值将是2,1,0（如果我们运行代码，因为我们处理的是数组，数组以0开头）。
交换算法基于当前位置的偶数或奇数值进行。如果您查看swap方法在哪里被调用，这是非常不言自明的。您可以看到发生了什么。
发生的情况如下：

public static void main(String[] args) {

        String ourword = "abc";
        String[] ourArray = ourword.split("");
        permute(ourArray, ourArray.length);

    }

    private static void swap(String[] ourarray, int right, int left) {
        String temp = ourarray[right];
        ourarray[right] = ourarray[left];
        ourarray[left] = temp;
    }

    public static void permute(String[] ourArray, int currentPosition) {
        if (currentPosition == 1) {
            System.out.println(Arrays.toString(ourArray));
        } else {
            for (int i = 0; i < currentPosition; i++) {
                // subtract one from the last position (here is where you are
                // selecting the the next last item 
                permute(ourArray, currentPosition - 1);

                // if it's odd position
                if (currentPosition % 2 == 1) {
                    swap(ourArray, 0, currentPosition - 1);
                } else {
                    swap(ourArray, i, currentPosition - 1);
                }
            }
        }
    }

java中的一个非常基本的解决方案是，如果要存储和返回解决方案字符串，请使用递归+集合（以避免重复）：

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

在这里和其他论坛给出的所有解决方案中，我最喜欢马克·拜尔斯。这个描述实际上让我自己思考并编写代码。可惜我不能说出他的解决方案，因为我是新手。
无论如何，这是我对他的描述的实现

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}

我更喜欢这个解决方案，因为这个解决方案使用了stringbuffer。我不会说我的解决方案没有创建任何临时字符串（实际上在 system.out.println 在哪里 toString() 调用stringbuffer的）。但我只是觉得这比第一个解决方案要好，第一个解决方案创建了太多的字符串文本。也许有人可以用“内存”来评估这一点（对于“时间”，由于额外的“交换”，它已经滞后了）

以下是我的解决方案，它基于《破解编码面试》（第54页）一书的思想：

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

正在运行字符串“d”的输出：
步骤1：合并[a]和[b:[ba，ab]
步骤2：合并[ba，ab]和c:[cba，bca，bac，cab，acb，]
步骤3：合并[cba、bca、bac、cab、acb、]和d:[dcba、cdba、cbda、cbad、dbca、bdca、bcda、bcad、dbac、bdac、badc、bacd、dcab、cdab、cabd、dacb、adcb、acdb、acbd、d、adbc、abdc、d]

使用递归。
依次尝试每个字母作为第一个字母，然后使用递归调用查找其余字母的所有排列。
基本情况是当输入为空字符串时，唯一的排列是空字符串。