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

}

我们可以用阶乘来计算有多少字符串以某个字母开头。

示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}

这个没有递归

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

在python中

def perms(in_str, prefix=""):
if not len(in_str) :
    print(prefix)
else:        
    for i in range(0, len(in_str)):
        perms(in_str[:i] + in_str[i + 1:], prefix + in_str[i])

perms('ASD')

使用递归。

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

简单的解决方案，利用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!)