Generar lista de todas las posibles permutaciones de una cadena
¿Cómo haría para generar una lista de todas las permutaciones posibles de una cadena entre caracteres x e y de longitud, que contenga una lista variable de caracteres?
Cualquier idioma funcionaría, pero debería ser portátil.
Hay varias formas de hacer esto. Los métodos comunes utilizan recursividad, memorización o programación dinámica. La idea básica es producir una lista de todas las cadenas de longitud 1, luego, en cada iteración, para todas las cadenas producidas en la última iteración, agregar esa cadena concatenada con cada carácter de la cadena individualmente. (el índice de variable en el código siguiente realiza un seguimiento del inicio de la última y la siguiente iteración)
Algún pseudocódigo:
list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
index = (index[1], len(list))
for string s in list.subset(index[0] to end):
for character c in originalString:
list.add(s + c)
Luego deberá eliminar todas las cadenas de longitud inferior a x; serán las primeras entradas (x-1) * len(originalString) de la lista.
Es mejor usar el retroceso
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}
Te van a salir muchos hilos, eso es seguro...
Donde x e y es cómo los defines y r es el número de caracteres que seleccionamos, si te entiendo correctamente. Definitivamente deberías generarlos según sea necesario y no ser descuidado y decir, generar un conjunto de potencia y luego filtrar la longitud de las cadenas.
La siguiente definitivamente no es la mejor manera de generarlos, pero de todos modos es un comentario interesante.
Knuth (volumen 4, fascículo 2, 7.2.1.3) nos dice que la combinación (s,t) es equivalente a s+1 cosas tomadas t a la vez con repetición; una combinación (s,t) es la notación utilizada por Knuth que es igual a . Podemos resolver esto generando primero cada combinación (s,t) en forma binaria (es decir, de longitud (s+t)) y contando el número de ceros a la izquierda de cada 1.
10001000011101 --> se convierte en la permutación: {0, 3, 4, 4, 4, 1}
