这里有一个优雅的，非递归的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;
    }

简单的解决方案，利用swift语言的特点，数组是值类型。

func permutation(chrs: [String], arr: [String], result: inout [[String]]) {
   if arr.count == chrs.count {
       result.append(arr)
       return
   }

   for chr in chrs {
       var arr = arr
       if !arr.contains(chr) {
           arr.append(chr)
           permutation(chrs: chrs, arr: arr, result: &result)
       }
   }
}

func test() {
   var result = [[String]]()
   let chrs = ["a", "b", "c", "d"]
   permutation(chrs: chrs, arr: [], result: &result)
}

复杂度O(n * n!)

/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

这是一个C解:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>


char* addLetter(char* string, char *c) {
    char* result = malloc(sizeof(string) + 2);
    strcpy(result, string);
    strncat(result, c, 1);
    return result;
}

char* removeLetter(char* string, char *c) {
    char* result = malloc(sizeof(string));
    int j = 0;
    for (int i = 0; i < strlen(string); i++) {
        if (string[i] != *c) {
            result[j++] = string[i];
        }
    }
    result[j] = '\0';

    return result;
}

void makeAnagram(char *anagram, char *letters) {

    if (*letters == '\0') {
        printf("%s\n", anagram);
        return;
    }

    char *c = letters;
    while (*c != '\0') {
        makeAnagram(addLetter(anagram, c),
                    removeLetter(letters, c));
        c++;
    }

}

int main() {

    makeAnagram("", "computer");

    return 0;
}

这可以通过简单地在前面部分结果的所有位置依次插入字符串的每个字母来迭代完成。

我们以[A]开头，与B连成[BA, AB]，与C连成[CBA, BCA, BAC, CAB等]。

运行时间将是O(n!)，对于测试用例ABCD，它是1 x 2 x 3 x 4。

在上面的乘积中，1是A, 2是B，以此类推。

飞镖示例:

void main() {

  String insertAt(String a, String b, int index)
  {
    return a.substring(0, index) + b + a.substring(index);
  }

  List<String> Permute(String word) {

    var letters = word.split('');

    var p_list = [ letters.first ];

    for (var c in letters.sublist(1)) {

      var new_list = [ ];

      for (var p in p_list)
        for (int i = 0; i <= p.length; i++)
          new_list.add(insertAt(p, c, i));

      p_list = new_list;
    }

    return p_list;
  }

  print(Permute("ABCD"));

}

在这里和其他论坛给出的所有解决方案中，我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案，因为我是新手。 无论如何，这是我对他的描述的实现

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中创建，其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说，由于额外的“交换”，它已经滞后了)