Generando todas las permutaciones de una cadena dada
¿Cuál es una forma elegante de encontrar todas las permutaciones de una cadena? Por ejemplo, la permutación de ba, sería bay ab, pero ¿qué pasa con cadenas más largas como abcdefgh? ¿Existe 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 programación en Java )
Utilice recursividad.
- Pruebe cada una de las letras como la primera letra y luego encuentre todas las permutaciones de las letras restantes usando una llamada recursiva.
- El caso base es que 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<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;
}
Ejecutando la salida de la cadena "abcd":
Paso 1: fusionar [a] y b: [ba, ab]
Paso 2: fusionar [ba, ab] y c: [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, la que más me gustó fue Mark Byers. Esa descripción realmente me hizo pensar y codificarla yo mismo. Lástima que no puedo votar a favor de su solución porque soy un 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,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);
}
}
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 (en realidad lo hace donde system.out.printlnse toString()llama a StringBuffer). Pero creo que esto es mejor que la primera solución en la que se crean demasiados literales de cadena. Puede que algún experto en rendimiento pueda evaluar esto en términos de "memoria" (para el "tiempo" ya se retrasa debido a ese "intercambio" adicional)
