生成给定字符串的所有排列

使用递归。

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

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编程入门)

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

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

示例:取输入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
}
}

让我们以输入abc为例。

从集合(["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());
}
}
}

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

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

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

改进的代码相同

    static String permutationStr[];
static int indexStr = 0;


static int factorial (int i) {
if (i == 1)
return 1;
else
return i * factorial(i-1);
}


public static void permutation(String str) {
char strArr[] = str.toLowerCase().toCharArray();
java.util.Arrays.sort(strArr);


int count = 1, dr = 1;
for (int i = 0; i < strArr.length-1; i++){
if ( strArr[i] == strArr[i+1]) {
count++;
} else {
dr *= factorial(count);
count = 1;
}
}
dr *= factorial(count);


count = factorial(strArr.length) / dr;


permutationStr = new String[count];


permutation("", str);


for (String oneStr : permutationStr){
System.out.println(oneStr);
}
}


private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
for (int i = 0; i < indexStr; i++){
if(permutationStr[i].equals(prefix))
return;
}
permutationStr[indexStr++] = prefix;
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
}

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
public static void main(String[] args) throws IOException {
hello h = new hello();
h.printcomp();
}
int fact=1;
public void factrec(int a,int k){
if(a>=k)
{fact=fact*k;
k++;
factrec(a,k);
}
else
{System.out.println("The string  will have "+fact+" permutations");
}
}
public void printcomp(){
String str;
int k;
Scanner in = new Scanner(System.in);
System.out.println("enter the string whose permutations has to b found");
str=in.next();
k=str.length();
factrec(k,1);
String[] arr =new String[fact];
char[] array = str.toCharArray();
while(p<fact)
printcomprec(k,array,arr);
// if incase u need array containing all the permutation use this
//for(int d=0;d<fact;d++)
//System.out.println(arr[d]);
}
int y=1;
int p = 0;
int g=1;
int z = 0;
public void printcomprec(int k,char array[],String arr[]){
for (int l = 0; l < k; l++) {
for (int b=0;b<k-1;b++){
for (int i=1; i<k-g; i++) {
char temp;
String stri = "";
temp = array[i];
array[i] = array[i + g];
array[i + g] = temp;
for (int j = 0; j < k; j++)
stri += array[j];
arr[z] = stri;
System.out.println(arr[z] + "   " + p++);
z++;
}
}
char temp;
temp=array[0];
array[0]=array[y];
array[y]=temp;
if (y >= k-1)
y=y-(k-1);
else
y++;
}
if (g >= k-1)
g=1;
else
g++;
}


}

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

以下是我在《破解编程面试》(P54)一书中提出的解决方案:

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

字符串"abcd"的运行输出:

• 步骤1:合并[a]和b: (ba, ab) < / p > < /李>

• 2 .合并[ba, ab]和c: [cba, bca, bac, cab, acb, abc]

. 第三步:合并[cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd]

这个没有递归

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

下面是一个简单的Java递归解决方案:

public static ArrayList<String> permutations(String s) {
ArrayList<String> out = new ArrayList<String>();
if (s.length() == 1) {
out.add(s);
return out;
}
char first = s.charAt(0);
String rest = s.substring(1);
for (String permutation : permutations(rest)) {
out.addAll(insertAtAllPositions(first, permutation));
}
return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
ArrayList<String> out = new ArrayList<String>();
for (int i = 0; i <= s.length(); ++i) {
String inserted = s.substring(0, i) + ch + s.substring(i);
out.add(inserted);
}
return out;
}

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

//Rotate and create words beginning with all letter possible and push to stack 1


//Read from stack1 and for each word create words with other letters at the next location by rotation and so on


/*  eg : man


1. push1 - man, anm, nma
2. pop1 - nma ,  push2 - nam,nma
pop1 - anm ,  push2 - amn,anm
pop1 - man ,  push2 - mna,man
*/


public class StringPermute {


static String str;
static String word;
static int top1 = -1;
static int top2 = -1;
static String[] stringArray1;
static String[] stringArray2;
static int strlength = 0;


public static void main(String[] args) throws IOException {
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
str = bfr.readLine();
word = str;
strlength = str.length();
int n = 1;
for (int i = 1; i <= strlength; i++) {
n = n * i;
}
stringArray1 = new String[n];
stringArray2 = new String[n];
push(word, 1);
doPermute();
display();
}


public static void push(String word, int x) {
if (x == 1)
stringArray1[++top1] = word;
else
stringArray2[++top2] = word;
}


public static String pop(int x) {
if (x == 1)
return stringArray1[top1--];
else
return stringArray2[top2--];
}


public static void doPermute() {


for (int j = strlength; j >= 2; j--)
popper(j);


}


public static void popper(int length) {
// pop from stack1 , rotate each word n times and push to stack 2
if (top1 > -1) {
while (top1 > -1) {
word = pop(1);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 2);
}
}
}
// pop from stack2 , rotate each word n times w.r.t position and push to
// stack 1
else {
while (top2 > -1) {
word = pop(2);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 1);
}
}
}


}


public static void rotate(int position) {
char[] charstring = new char[100];
for (int j = 0; j < word.length(); j++)
charstring[j] = word.charAt(j);


int startpos = strlength - position;
char temp = charstring[startpos];
for (int i = startpos; i < strlength - 1; i++) {
charstring[i] = charstring[i + 1];
}
charstring[strlength - 1] = temp;
word = new String(charstring).trim();
}


public static void display() {
int top;
if (top1 > -1) {
while (top1 > -1)
System.out.println(stringArray1[top1--]);
} else {
while (top2 > -1)
System.out.println(stringArray2[top2--]);
}
}
}

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

我们从[A]开始，加上B就变成了[BA, AB]，加上C就变成了[CBA, BCA, BAC, CAB, etc]。

运行时间将是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"));


}

import java.io.*;
public class Anagram {


public static void main(String[] args) {
java.util.Scanner sc=new java.util.Scanner(System.in);
PrintWriter p=new PrintWriter(System.out,true);
p.println("Enter Word");
String a[],s="",st;boolean flag=true;
int in[],n,nf=1,i,j=0,k,m=0;
char l[];
st=sc.next();
p.println("Anagrams");
p.println("1 . "+st);
l=st.toCharArray();
n=st.length();
for(i=1;i<=n;i++){
nf*=i;
}


i=1;
a=new String[nf];
in=new int[n];
a[0]=st;
while(i<nf){
for(m=0;m<n;m++){
in[m]=n;
}j=0;
while(j<n){
k=(int)(n*Math.random());


for(m=0;m<=j;m++){
if(k==in[m]){
flag=false;
break;
}
}
if(flag==true){
in[j++]=k;
}flag=true;
}s="";
for(j=0;j<n;j++){
s+=l[in[j]];
}


//Removing same words
for(m=0;m<=i;m++){
if(s.equalsIgnoreCase(a[m])){
flag=false;
break;
}
}
if(flag==true){
a[i++]=s;
p.println(i+" . "+a[i-1]);
}flag=true;


}


}
}

/*
* eg: abc =>{a,bc},{b,ac},{c,ab}
* =>{ca,b},{cb,a}
* =>cba,cab
* =>{ba,c},{bc,a}
* =>bca,bac
* =>{ab,c},{ac,b}
* =>acb,abc
*/
public void nonRecpermute(String prefix, String word)
{
String[] currentstr ={prefix,word};
Stack<String[]> stack = new Stack<String[]>();
stack.add(currentstr);
while(!stack.isEmpty())
{
currentstr = stack.pop();
String currentPrefix = currentstr[0];
String currentWord = currentstr[1];
if(currentWord.equals(""))
{
System.out.println("Word ="+currentPrefix);
}
for(int i=0;i<currentWord.length();i++)
{
String[] newstr = new String[2];
newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
newstr[1] = currentWord.substring(0, i);
if(i<currentWord.length()-1)
{
newstr[1] = newstr[1]+currentWord.substring(i+1);
}
stack.push(newstr);
}


}


}

注意:上述递归函数将从起始索引中调用。

private void PrintAllPermutations(int[] a, int index, ref int count)
{
if (index == (a.Length - 1))
{
count++;
var s = string.Format("{0}: {1}", count, string.Join(",", a));
Debug.WriteLine(s);
}
for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
this.PrintAllPermutations(a, index + 1, ref count);
Utilities.swap(ref a[i], ref a[index]);
}
}
private int PrintAllPermutations(int[] a)
{
a.ThrowIfNull("a");
int count = 0;
this.PrintAllPermutations(a, index:0, count: ref count);
return count;
}

版本2(与上面相同-但返回排列而不是打印)

private int[][] GetAllPermutations(int[] a, int index)
{
List<int[]> permutations = new List<int[]>();
if (index == (a.Length - 1))
{
permutations.Add(a.ToArray());
}


for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
var r = this.GetAllPermutations(a, index + 1);
permutations.AddRange(r);
Utilities.swap(ref a[i], ref a[index]);
}
return permutations.ToArray();
}
private int[][] GetAllPermutations(int[] p)
{
p.ThrowIfNull("p");
return this.GetAllPermutations(p, 0);
}

单元测试

[TestMethod]
public void PermutationsTests()
{
List<int> input = new List<int>();
int[] output = { 0, 1, 2, 6, 24, 120 };
for (int i = 0; i <= 5; i++)
{
if (i != 0)
{
input.Add(i);
}
Debug.WriteLine("================PrintAllPermutations===================");
int count = this.PrintAllPermutations(input.ToArray());
Assert.IsTrue(count == output[i]);
Debug.WriteLine("=====================GetAllPermutations=================");
var r = this.GetAllPermutations(input.ToArray());
Assert.IsTrue(count == r.Length);
for (int j = 1; j <= r.Length;j++ )
{
string s = string.Format("{0}: {1}", j,
string.Join(",", r[j - 1]));
Debug.WriteLine(s);
}
Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count);
}
}

下面是一个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

所有之前的贡献者都很好地解释和提供了代码。我想我也应该分享这个方法，因为它可能也会帮助到别人。解决方案基于(堆的算法)

一些事情:

1. 注意excel中最后一项的描述只是为了帮助你更好地可视化逻辑。因此，最后一列的实际值将是2,1,0(如果我们要运行代码，因为我们处理的是数组，而数组以0开头)。

2. 交换算法基于当前位置的偶数或奇数值发生。如果你看一下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);
}
}
}
}

使用递归。

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

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

另一种简单的方法是遍历字符串，选择尚未使用的字符并将其放入缓冲区，继续循环，直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案，因为:

1. 容易理解
2. 容易避免重复
3. 输出是排序的

下面是java代码:

List<String> permute(String str) {
if (str == null) {
return null;
}


char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];


List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();


Arrays.sort(chars);


helper(chars, used, sb, res);


return res;
}


void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}


for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}


// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);


helper(chars, used, sb, res);


// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}

输入str: 1231

输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}

注意，输出是排序的，没有重复的结果。

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

递归是不必要的，即使你可以计算任何直接排列，这个解决方案使用泛型来排列任何数组。

在这里是关于这个算法的一个很好的信息。

对于c#开发人员来说，在这里是更有用的实现。

public static void main(String[] args) {
String word = "12345";


Character[] array = ArrayUtils.toObject(word.toCharArray());
long[] factorials = Permutation.getFactorials(array.length + 1);


for (long i = 0; i < factorials[array.length]; i++) {
Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
printPermutation(permutation);
}
}


private static void printPermutation(Character[] permutation) {
for (int i = 0; i < permutation.length; i++) {
System.out.print(permutation[i]);
}
System.out.println();
}

该算法具有O (N) 时间和空间的复杂度来计算每个排列。

public class Permutation {
public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
T[] permutation = generatePermutation(array, sequence);


return permutation;
}


public static <T> T[] generatePermutation(T[] array, int[] sequence) {
T[] clone = array.clone();


for (int i = 0; i < clone.length - 1; i++) {
swap(clone, i, i + sequence[i]);
}


return clone;
}


private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
int[] sequence = new int[size];


for (int j = 0; j < sequence.length; j++) {
long factorial = factorials[sequence.length - j];
sequence[j] = (int) (permutationNumber / factorial);
permutationNumber = (int) (permutationNumber % factorial);
}


return sequence;
}


private static <T> void swap(T[] array, int i, int j) {
T t = array[i];
array[i] = array[j];
array[j] = t;
}


public static long[] getFactorials(int length) {
long[] factorials = new long[length];
long factor = 1;


for (int i = 0; i < length; i++) {
factor *= i <= 1 ? 1 : i;
factorials[i] = factor;
}


return factorials;
}
}

这是一个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;
}

这对我很有效。

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

我的实现基于Mark Byers上面的描述:

    static Set<String> permutations(String str){
if (str.isEmpty()){
return Collections.singleton(str);
}else{
Set <String> set = new HashSet<>();
for (int i=0; i<str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
set.add(str.charAt(i) + s);
return set;
}
}

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[]) {
permu(0,"ABCD");
}


static void permu(int fixed,String s) {
char[] chr=s.toCharArray();
if(fixed==s.length())
System.out.println(s);
for(int i=fixed;i<s.length();i++) {
char c=chr[i];
chr[i]=chr[fixed];
chr[fixed]=c;
permu(fixed+1,new String(chr));
}
}

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

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

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](Combination of abc)->。

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

然后递归调用每个[bc]，[ac] &[ab]独立。

这是一个具有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);


}

｝

public static List<String> stringPermutation(String s) {
List<String> results = new ArrayList<>();
Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet());
stringPermutation(charSet, "", results);
return results;
}


private static void stringPermutation(Set<Character> charSet,
String prefix, List<String> results) {
if (charSet.isEmpty()) {
results.add(prefix);
return;
}
for (Character c : charSet) {
Set<Character> newSet = new HashSet<>(charSet);
newSet.remove(c);
stringPermutation(newSet, prefix + c, results);
}
}

该代码可以泛化为一组对象查找排列。在本例中，我使用了一组颜色。

public enum Color{
ORANGE,RED,BULE,GREEN,YELLOW;
}


public static List<List<Color>> colorPermutation(Set<Color> colors) {
List<List<Color>> results = new ArrayList<>();
List<Color> prefix = new ArrayList<>();
permutation(colors, prefix, results);
return results;
}


private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) {
if (set.isEmpty()) {
results.add(prefix);
return;
}
for (T t : set) {
Set<T> newSet = new HashSet<>(set);
List<T> newPrefix = new ArrayList<>(prefix);
newSet.remove(t);
newPrefix.add(t);
permutation(newSet, newPrefix, results);
}
}

测试代码。

public static void main(String[] args) {
List<String> stringPerm = stringPermutation("abcde");
System.out.println("# of permutations:" + stringPerm.size());
stringPerm.stream().forEach(e -> System.out.println(e));


Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet());
List<List<Color>> colorPerm = colorPermutation(colorSet);
System.out.println("# of permutations:" + colorPerm.size());
colorPerm.stream().forEach(e -> System.out.println(e));
}

为排列和组合添加更详细的NcK/NcR

public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);


// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}


public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) {
for (int count = 0; count < inputList.size(); count++) {
permNcK(inputList, "", chooseCount, resultList);
resultList = new ArrayList<String>();
Collections.rotate(inputList, 1);
System.out.println("-------------------------");
}


}


public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);


// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}


public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" });
List<String> resultList = new ArrayList<String>();
//combinationNcK(positions, "", 3, resultList);


permNcK(positions, 3, resultList);


}

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1，因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
{
if(str==null)
return;
Set<String> StrList = new HashSet<String>();
StringBuilder strB= new StringBuilder();
for(int i = 0;i < (1 << str.length()); ++i)
{
strB.setLength(0); //clear the StringBuilder
for(int j = 0;j < str.length() ;++j){
if((i & (1 << j))>0){  // to check whether jth bit is set
strB.append(str.charAt(j));
}
}
if(!strB.toString().isEmpty())
StrList.add(strB.toString());
}
System.out.println(Arrays.toString(StrList.toArray()));
}

这是一个更快的解决方案，因为它不受字符串连接计算复杂度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);
}

使用递归的简单python解决方案。

def get_permutations(string):


# base case
if len(string) <= 1:
return set([string])


all_chars_except_last = string[:-1]
last_char = string[-1]


# recursive call: get all possible permutations for all chars except last
permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)


# put the last char in all possible positions for each of the above permutations
permutations = set()
for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
for position in range(len(all_chars_except_last) + 1):
permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
permutations.add(permutation)


return permutations

基于马克·拜尔斯的回答，我的python实现:

def permutations(string):
if len(string) == 1:
return [string]
permutations=[]
for i in range(len(string)):
for perm in permutations(string[:i]+string[i+1:]):
permutations.append(string[i] + perm)
return permutations

没有递归的Java实现

public Set<String> permutate(String s){
Queue<String> permutations = new LinkedList<String>();
Set<String> v = new HashSet<String>();
permutations.add(s);


while(permutations.size()!=0){
String str = permutations.poll();
if(!v.contains(str)){
v.add(str);
for(int i = 0;i<str.length();i++){
String c = String.valueOf(str.charAt(i));
permutations.add(str.substring(i+1) + c +  str.substring(0,i));
}
}
}
return v;
}

递归Python解决方案

def permute(input_str):
_permute("", input_str)


def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)


else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])


if __name__ == '__main__':
permute('foobar')

倒计时Quickperm算法的泛型实现，表示#1(可伸缩，非递归)。

/**
* Generate permutations based on the
* Countdown <a href="http://quickperm.org/">Quickperm algorithm</>.
*/
public static <T> List<List<T>> generatePermutations(List<T> list) {
List<T> in = new ArrayList<>(list);
List<List<T>> out = new ArrayList<>(factorial(list.size()));


int n = list.size();
int[] p = new int[n +1];
for (int i = 0; i < p.length; i ++) {
p[i] = i;
}
int i = 0;
while (i < n) {
p[i]--;
int j = 0;
if (i % 2 != 0) { // odd?
j = p[i];
}
// swap
T iTmp = in.get(i);
in.set(i, in.get(j));
in.set(j, iTmp);


i = 1;
while (p[i] == 0){
p[i] = i;
i++;
}
out.add(new ArrayList<>(in));
}
return out;
}


private static int factorial(int num) {
int count = num;
while (num != 1) {
count *= --num;
}
return count;
}

它需要list，因为泛型不能很好地使用数组。

这是另一个更简单的方法来做一个字符串的排列。

public class Solution4 {
public static void main(String[] args) {
String  a = "Protijayi";
per(a, 0);


}


static void per(String a  , int start ) {
//bse case;
if(a.length() == start) {System.out.println(a);}
char[] ca = a.toCharArray();
//swap
for (int i = start; i < ca.length; i++) {
char t = ca[i];
ca[i] = ca[start];
ca[start] = t;
per(new String(ca),start+1);
}


}//per


}

一个java实现打印给定字符串的所有排列，考虑重复字符，只打印唯一字符，如下所示:

import java.util.Set;
import java.util.HashSet;


public class PrintAllPermutations2
{
public static void main(String[] args)
{
String str = "AAC";


PrintAllPermutations2 permutation = new PrintAllPermutations2();


Set<String> uniqueStrings = new HashSet<>();


permutation.permute("", str, uniqueStrings);
}


void permute(String prefixString, String s, Set<String> set)
{
int n = s.length();


if(n == 0)
{
if(!set.contains(prefixString))
{
System.out.println(prefixString);
set.add(prefixString);
}
}
else
{
for(int i=0; i<n; i++)
{
permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
}
}
}
}

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

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

使用Es6的字符串排列

使用reduce()方法

const permutations = str => {
if (str.length <= 2)
return str.length === 2 ? [str, str[1] + str[0]] : [str];
  

return str
.split('')
.reduce(
(acc, letter, index) =>
acc.concat(permutations(str.slice(0, index) + str.slice(index + 1)).map(val => letter + val)),
[]
);
};


console.log(permutations('STR'));

如果有人想要生成排列来做一些事情，而不是通过void方法打印它们:

static List<int[]> permutations(int n) {


class Perm {
private final List<int[]> permutations = new ArrayList<>();


private void perm(int[] array, int step) {
if (step == 1) permutations.add(array.clone());
else for (int i = 0; i < step; i++) {
perm(array, step - 1);
int j = (step % 2 == 0) ? i : 0;
swap(array, step - 1, j);
}
}


private void swap(int[] array, int i, int j) {
int buffer = array[i];
array[i] = array[j];
array[j] = buffer;
}


}


int[] nVector  = new int[n];
for (int i = 0; i < n; i++) nVector [i] = i;


Perm perm = new Perm();
perm.perm(nVector, n);
return perm.permutations;


}

简单的递归c++实现如下所示:

#include <iostream>


void generatePermutations(std::string &sequence, int index){
if(index == sequence.size()){
std::cout << sequence << "\n";
} else{
generatePermutations(sequence, index + 1);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1);
std::swap(sequence[index], sequence[i]);
}
}
}


int main(int argc, char const *argv[])
{
std::string str = "abc";
generatePermutations(str, 0);
return 0;
}

输出:

abc
acb
bac
bca
cba
cab

更新

如果想要存储结果，可以将vector作为函数调用的第三个参数。此外，如果你只想要唯一的排列，你可以使用set。

#include <iostream>
#include <vector>
#include <set>


void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){
if(index == sequence.size()){
//std::cout << sequence << "\n";
v.push_back(sequence);
} else{
generatePermutations(sequence, index + 1, v);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1, v);
std::swap(sequence[index], sequence[i]);
}
}
}


int main(int argc, char const *argv[])
{
std::string str = "112";
std::vector <std::string> permutations;
generatePermutations(str, 0, permutations);
std::cout << "Number of permutations " << permutations.size() << "\n";
for(const std::string &s : permutations){
std::cout << s << "\n";
}
std::set <std::string> uniquePermutations(permutations.begin(), permutations.end());
std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n";
for(const std::string &s : uniquePermutations){
std::cout << s << "\n";
}
return 0;
}

输出:

Number of permutations 6
112
121
112
121
211
211
Number of unique permutations 3
112
121
211

public class Permutation
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n-1);
}


/**
* permutation function
* @param str string to calculate permutation for
* @param l starting index
* @param r end index
*/
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}


/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}


}

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

我定义了左右两个字符串。一开始，左边是输入字符串，右边是“”。我递归地从左边选择所有可能的字符，并将其添加到右边的末尾。然后，在left-charAt(I)和right+charAt(I)上调用递归函数。我定义了一个类来跟踪生成的排列。

import java.util.HashSet;
import java.util.Set;


public class FindPermutations {


static class Permutations {
Set<String> permutations = new HashSet<>();
}


/**
* Building all the permutations by adding chars of left to right one by one.
*
* @param left         The left string
* @param right        The right string
* @param permutations The permutations
*/
private void findPermutations(String left, String right, Permutations permutations) {
int n = left.length();
if (n == 0) {
permutations.permutations.add(right);
}
for (int i = 0; i < n; i++) {
findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations);
}
}


/**
* Gets all the permutations of a string s.
*
* @param s The input string
* @return all the permutations of a string s
*/
public Permutations getPermutations(String s) {
Permutations permutations = new Permutations();
findPermutations(s, "", permutations);
return permutations;
}


public static void main(String[] args) {
FindPermutations findPermutations = new FindPermutations();
String s = "ABC";
Permutations permutations = findPermutations.getPermutations(s);
printPermutations(permutations);
}


private static void printPermutations(Permutations permutations) {
for (String p : permutations.permutations) {
System.out.println(p);
}
}


}

我希望这能有所帮助。

作为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)

基于马克·拜尔斯的回答，我提出了这个解决方案:

JAVA

public class Main {


public static void main(String[] args) {
myPerm("ABCD", 0);
}


private static void myPerm(String str, int index)
{
if (index == str.length()) System.out.println(str);


for (int i = index; i < str.length(); i++)
{
char prefix = str.charAt(i);
String suffix = str.substring(0,i) + str.substring(i+1);


myPerm(prefix + suffix, index + 1);
}
}
}

c#

我还使用新的c# 8.0范围操作符在c#中编写了这个函数

    class Program
{
static void Main(string[] args)
{
myPerm("ABCD", 0);
}


private static void myPerm(string str, int index)
{
if (index == str.Length) Console.WriteLine(str);


for (int i = index; i < str.Length; i++)
{
char prefix = str[i];
string suffix = str[0..i] + str[(i + 1)..];


myPerm(prefix + suffix, index + 1);
}
}
    

我们只是把每个字母放在开头，然后排列。
第一次迭代是这样的:

/*
myPerm("ABCD",0)
prefix = "A"
suffix = "BCD"
myPerm("ABCD",1)
prefix = "B"
suffix = "ACD"
myPerm("BACD",2)
prefix = "C"
suffix = "BAD"
myPerm("CBAD",3)
prefix = "D"
suffix = "CBA"
myPerm("DCBA",4)
Console.WriteLine("DCBA")
*/

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

给定一个字符串，比如'abc'，把它分解成一个子问题，寻找一个字符串的排列少一个字符，即'bc'。一旦我们有了bc的排列，我们需要知道如何把它和a结合起来，得到abc的排列。这是递归的核心。用子问题的解来解决当前问题。通过观察，我们可以看到，在'bc'的每个排列的所有位置(即'bc'和'cb')插入'a'，就可以得到'abc'的所有排列。我们必须在相邻的字母之间，在每个排列的前面和末尾插入'a'。例如

我们有bc

'a'+'bc' = 'abc'

'b'+'a'+'c' = 'bac'

'bc'+'a' = 'bca'

对于'cb'我们有

'a'+'cb' = 'acb'

'c'+'a'+'b' = 'cab'

'cb'+'a' = 'cba'

下面的代码片段将说明这一点。在这里是代码片段的工作链接。

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

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


}