Generando todas las permutaciones de una cadena dada

¿Cuál es una forma elegante de encontrar todas las permutaciones de una cadena? Por ejemplo, ba , sería ba y ab , pero ¿qué tal abcdefgh ? ¿Hay algún ejemplo de implementación de Java?

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

(a través de Introducción a la Progtwigción en Java )

Use recursión.

  • Pruebe cada una de las letras a su vez como la primera letra y luego encuentre todas las permutaciones de las letras restantes mediante una llamada recursiva.
  • El caso base es cuando la entrada es una cadena vacía, la única permutación es la cadena vacía.

Aquí está mi solución que se basa en la idea del libro “Cracking the Coding Interview” (P54):

 /** * List permutations of a string. * * @param s the input string * @return the list of permutations */ public static ArrayList permutation(String s) { // The result ArrayList res = new ArrayList(); // 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, eg {"ab", "ba"} * @param c the last character * @return a merged new list, eg {"cab", "acb" ... } */ public static ArrayList merge(ArrayList list, String c) { ArrayList 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; } 

Ejecución de la salida de la cadena "abcd":

  • Paso 1: Fusionar [a] y b: [ba, ab]

  • Paso 2: Fusionar [ba, ab] yc: [cba, bca, bac, cab, acb, abc]

  • Paso 3: Fusionar [cba, bca, bac, cab, acb, abc] y 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]

De todas las soluciones dadas aquí y en otros foros, Mark Byers me gustó más. Esa descripción realmente me hizo pensar y codificar yo mismo. Lástima que no puedo votar su solución ya que soy novato.
De todos modos aquí está mi implementación de su descripción

 public class PermTest { public static void main(String[] args) throws Exception { String str = "abcdef"; StringBuffer strBuf = new StringBuffer(str); doPerm(strBuf,str.length()); } private static void doPerm(StringBuffer str, int index){ if(index <= 0) System.out.println(str); else { //recursively solve this by placing all other chars at current first pos doPerm(str, index-1); int currPos = str.length()-index; for (int i = currPos+1; i < str.length(); i++) {//start swapping all other chars with current first char swap(str,currPos, i); doPerm(str, index-1); swap(str,i, currPos);//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); } } 

Prefiero esta solución antes que la primera en este hilo porque esta solución usa StringBuffer. No diría que mi solución no crea ninguna cadena temporal (realmente lo hace en system.out.println donde se system.out.println toString() de StringBuffer). Pero siento que esto es mejor que la primera solución donde se crean demasiados literales de cadenas. Puede ser un tipo de rendimiento que pueda evaluar esto en términos de 'memoria' (por 'tiempo' ya está retrasado debido a ese 'intercambio' extra)

Una solución muy básica en Java es usar recursion + Set (para evitar repeticiones) si desea almacenar y devolver las cadenas de solución:

 public static Set generatePerm(String input) { Set set = new HashSet(); if (input == "") return set; Character a = input.charAt(0); if (input.length() > 1) { input = input.substring(1); Set 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; } 

Todos los colaboradores anteriores han hecho un gran trabajo al explicar y proporcionar el código. Pensé que debería compartir este enfoque también porque podría ayudar a alguien también. La solución se basa en ( algoritmo de montones )

Un par de cosas:

  1. Tenga en cuenta que el último elemento que se muestra en Excel es solo para ayudarlo a visualizar mejor la lógica. Entonces, los valores reales en la última columna serían 2,1,0 (si tuviéramos que ejecutar el código porque estamos tratando con matrices y las matrices comienzan con 0).

  2. El algoritmo de intercambio ocurre en función de los valores pares o impares de la posición actual. Se explica por sí mismo si observa dónde se llama el método de intercambio. Puede ver lo que está sucediendo.

Esto es lo que sucede: enter image description here

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

Este es sin recursión

 public static void permute(String s) { if(null==s || s.isEmpty()) { return; } // List containing words formed in each iteration List strings = new LinkedList(); 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 tempList = new LinkedList(); for(int i=1; i< s.length(); i++) { for(int j=0; j merge(Character c, String s) { if(s==null || s.isEmpty()) { return null; } int len = s.length(); StringBuilder sb = new StringBuilder(); Set list = new HashSet(); 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; } 

Usemos el abc entrada como ejemplo.

Comience con solo el último elemento ( c ) en un conjunto ( ["c"] ), luego agregue el segundo último elemento ( b ) a su frente, final y todas las posiciones posibles en el centro, por lo que es ["bc", "cb"] y luego de la misma manera agregará el siguiente elemento de la parte posterior ( a ) a cada cadena en el conjunto que lo hace:

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

Por lo tanto, permutación completa:

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

Código:

 public class Test { static Set permutations; static Set result = new HashSet(); public static Set permutation(String string) { permutations = new HashSet(); 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 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(); } } public static void main(String[] args) { Set result = permutation("abc"); System.out.println("\nThere are total of " + result.size() + " permutations:"); Iterator it = result.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } 

Bueno, aquí hay una solución elegante, no recursiva, 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; } 

Una de las soluciones simples podría ser simplemente intercambiar los caracteres recursivamente con dos punteros.

 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 

esto funcionó para mí …

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

Use recursión.

cuando la entrada es una cadena vacía, la única permutación es una cadena vacía. Pruebe cada una de las letras de la cadena haciéndola como la primera letra y luego encuentre todas las permutaciones de las letras restantes mediante una llamada recursiva.

 import java.util.ArrayList; import java.util.List; class Permutation { private static List permutation(String prefix, String str) { List 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 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); } } } 

implementación 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','') 
 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= 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 permute(String s) { ArrayList 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; } 

Aquí hay una solución recursiva minimalista y directa en Java:

 public static ArrayList permutations(String s) { ArrayList out = new ArrayList(); 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 insertAtAllPositions(char ch, String s) { ArrayList out = new ArrayList(); for (int i = 0; i <= s.length(); ++i) { String inserted = s.substring(0, i) + ch + s.substring(i); out.add(inserted); } return out; } 

Esto es lo que hice a través de la comprensión básica de las permutaciones y la función de llamada recursiva. Toma un poco de tiempo pero se hace de forma independiente.

 public class LexicographicPermutations { public static void main(String[] args) { // TODO Auto-generated method stub String s="abc"; Listcombinations=new ArrayList(); combinations=permutations(s); Collections.sort(combinations); System.out.println(combinations); } private static List permutations(String s) { // TODO Auto-generated method stub Listcombinations=new ArrayList(); if(s.length()==1){ combinations.add(s); } else{ for(int i=0;itemp=permutations(s.substring(0, i)+s.substring(i+1)); for (String string : temp) { combinations.add(s.charAt(i)+string); } } } return combinations; }} 

que genera Salida como [abc, acb, bac, bca, cab, cba] .

La lógica básica detrás de esto es

Para cada personaje, considéralo como 1er personaje y encuentra las combinaciones de los personajes restantes. por ejemplo [abc](Combination of abc)-> .

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

Y luego recursivamente llamando a cada [bc] , [ac] y [ab] independiente.

Implementación de Java sin recursión

 public Set permutate(String s){ Queue permutations = new LinkedList(); Set v = new HashSet(); permutations.add(s); while(permutations.size()!=0){ String str = permutations.poll(); if(!v.contains(str)){ v.add(str); for(int i = 0;i 
 //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 wrt 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--]); } } } 

Podemos usar factorial para encontrar cuántas cadenas comenzaron con una letra particular.

Ejemplo: tomar la entrada abcd . (3!) == 6 cadenas comenzarán con cada letra de 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 } } 

Aquí hay una implementación de Java:

 /* All Permutations of a String */ import java.util.*; import java.lang.*; import java.io.*; /* Complexity O(n*n!) */ class Ideone { public static ArrayList strPerm(String str, ArrayList 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 list = new ArrayList<>(); list = strPerm(str,list); System.out.println("Total Permutations : "+list.size()); for(int i=0;i 

http://ideone.com/nWPb3k

La recursividad no es necesaria, incluso si puede calcular cualquier permutación directamente , esta solución utiliza generics para permutar cualquier matriz.

Aquí hay una buena información sobre este algoritmo.

Para los desarrolladores de C # aquí hay una implementación más útil.

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

Este algoritmo tiene una complejidad de tiempo y espacio O (N) para calcular cada permutación .

 public class Permutation { public static  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[] 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  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; } } 

Permutación de String:

 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 

Una implementación java para imprimir todas las permutaciones de una cadena dada teniendo en cuenta los caracteres duplicados e imprime solo caracteres únicos es la siguiente:

 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 uniqueStrings = new HashSet<>(); permutation.permute("", str, uniqueStrings); } void permute(String prefixString, String s, Set 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 

// inserte cada carácter en una lista de arrays

 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) + " "); } } 
 /* * 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 stack = new Stack(); 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 

Esto se puede hacer de forma iterativa simplemente insertando cada letra de la cadena a su vez en todas las ubicaciones de los resultados parciales anteriores.

Comenzamos con [A] , que con B convierte en [BA, AB] , y con C , [CBA, BCA, BAC, CAB, etc] .

El tiempo de ejecución sería O(n!) , Que, para el caso de prueba ABCD , es 1 x 2 x 3 x 4 .

En el producto anterior, el 1 es para A , el 2 es para B , etc.

Dart muestra:

 void main() { String insertAt(String a, String b, int index) { return a.substring(0, index) + b + a.substring(index); } List 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")); } 

Aquí hay dos versiones de c # (solo como referencia): 1. Imprime todas las permuaciones 2. devuelve todas las permutaciones

La esencia básica del algoritmo es (probablemente debajo del código sea más intuitivo, sin embargo, aquí hay una explicación de lo que hace el código siguiente): – del índice actual al rest de la colección, intercambie el elemento al índice actual – obtenga las permutaciones para los elementos restantes del siguiente índice recursivamente, restaure el orden, volviendo a intercambiar

Nota: la función recursiva anterior se invocará desde el índice de inicio.

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

versión 2 (igual que la anterior, pero devuelve las permutaciones en lugar de imprimir)

 private int[][] GetAllPermutations(int[] a, int index) { List permutations = new List(); 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); } 

Unit Tests

 [TestMethod] public void PermutationsTests() { List input = new List(); 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); } } 

Another simple way is to loop through the string, pick the character that is not used yet and put it to a buffer, continue the loop till the buffer size equals to the string length. I like this back tracking solution better because:

  1. Easy to understand
  2. Easy to avoid duplication
  3. The output is sorted

Here is the java code:

 List permute(String str) { if (str == null) { return null; } char[] chars = str.toCharArray(); boolean[] used = new boolean[chars.length]; List res = new ArrayList(); StringBuilder sb = new StringBuilder(); Arrays.sort(chars); helper(chars, used, sb, res); return res; } void helper(char[] chars, boolean[] used, StringBuilder sb, List 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; } } } 

Input str: 1231

Output list: {1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211}

Noticed that the output is sorted, and there is no duplicate result.

This is a C solution:

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