这是一个更快的解决方案，因为它不受字符串连接计算复杂度O(n^2)的影响。另一方面它是无循环的，完全递归的

public static void main(String[] args) {
    permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}

private static void permutation(String str) {
    char[] stringArray = str.toCharArray();
    printPermutation(stringArray, 0, stringArray.length, 0, 1);
}

private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) {
    // Stop condition
    if (loopCounter == length)
        return;

    /* 
     When reaching the end of the array:
     1- Reset loop indices.
     2- Increase length counter. 
    */ 
    if (indexTo == length) {
        indexFrom = 0;
        indexTo = 1;
        ++loopCounter;
    }

    // Print.
    System.out.println(string);

    // Swap from / to indices.
    char temp = string[indexFrom];
    string[indexFrom] = string[indexTo];
    string[indexTo] = temp;

    // Go for next iteration.
    printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo);
}

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

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

让我试着用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的列表进行排列，因此我们所需要做的就是将它们分解为这些大小中的任何一个，并将它们正确地组合起来。想象一台头奖机器:这个算法将从右向左旋转，然后写下

当列表大小为0或1时，返回空/列表为1 当列表大小为2时处理(例如[3,4])，并生成2个排列([3,4]& [4,3]) 对于每一项，将其标记为最后一项中的最后一项，并找到列表中其余项目的所有排列。(例如，把[4]放在桌子上，把[1,2,3]重新排列) 现在对它的子元素进行所有的排列，把它自己放回列表的末尾(例如:[1,2,3][，4]，[1,3,2][，4]，[2,3,1][，4]，…)

基于Heap算法的我的实现:

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

public class PermutationString {
public static List<String> permute(char[] str, int n) {
    List<String> permutations = new ArrayList<>();
    if (n == 1) {
        permutations.add(new String(str));
    }
    else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permute(str, n-1));
            if (n % 2 == 0) {
                swap(str, i, n-1);
            }
            else {
                swap(str, 0, n-1);
            }
        }
    }
    return permutations;
}


public static void swap(char[] str, int i, int j) {
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

public static void main(String[] args) {

    List<String> permutations = permute("abcdefgh".toCharArray(), 8);

    System.out.println(permutations);

}
}

时间复杂度为O(n!* n)， O(n)为空间复杂度。

下面是一个java实现:

/* All Permutations of a String */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Complexity O(n*n!) */
class Ideone
{
     public static ArrayList<String> strPerm(String str, ArrayList<String> list)
     {
        int len = str.length();
        if(len==1){
            list.add(str);
            return list;
        }

        list = strPerm(str.substring(0,len-1),list);
        int ls = list.size();
        char ap = str.charAt(len-1);
        for(int i=0;i<ls;i++){
            String temp = list.get(i);
            int tl = temp.length();
            for(int j=0;j<=tl;j++){
                list.add(temp.substring(0,j)+ap+temp.substring(j,tl));  
            }
        }

        while(true){
            String temp = list.get(0);
            if(temp.length()<len)
                list.remove(temp);
            else
                break;
        }

        return list;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        String str = "abc";
        ArrayList<String> list = new ArrayList<>();

        list = strPerm(str,list);
        System.out.println("Total Permutations : "+list.size());
        for(int i=0;i<list.size();i++)
            System.out.println(list.get(i));

    }
}

http://ideone.com/nWPb3k

使用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));