Algoritmia - Algoritmo de Permutaciones

   
Vista:

Algoritmo de Permutaciones

Publicado por Raul (1 intervención) el 06/12/2007 16:03:51
Buenas, me gustaría hacer una algoritmo que, dados unos strings almacenados en arrays según su tamaño, me hiciese todas las permutaciones possibles. El objetivo es comprobar si una permutación determinada cumple una condición sin pasarse de un tamaño N, y si es así apartarlo.
Por ejemplo, si tengo 1 string de tamaño 2, 3 strings de tamaño 3, y uno de tamaño 4, las permutaciones posibles para N=9 serían:

2-3-4
3-3-3

La idea intuitiva es:

for (int i=0; i<NumerodeArrays cuyos Strings son menors que N; i++){
arr = arrayConStringsDeTamaño(i);
for (int j=0; j<NumerodeStrings; j++){
s= arr[j];
for (int k=i; k<NumerodeArrays; k++){
arr2=arrayConStringsDeTamaño(k);
for (int l=i; l<NumerodeArrays; l++){
s2=arr2[l];;
si (s2 cumple condicion){
s= concatenar s2 con s
}
}
}
}
}

Como podreis observar, esto funciona razonablemente hasta que N es 15 o por ahí.

Si alguien se le ocurre algo más eficiente le estaría eternamente agradecido.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:Algoritmo de Permutaciones

Publicado por Alexander Pinzon (1 intervención) el 28/07/2008 21:43:31
Si hay una solucion para permutar palabras de tamaño N

////****** l = longitud de la cadena
l = len(cad);
factorial de n n!, o fact(n);
funcion residuo mod o %

una cadena tiene n! permutaciones si su longitud es n
para la permutacion X, X pertenece al intervalo [1, 2, 3, ..., n!]
y para la posicion m-esima en la cadena m pertenece [0,1,2, ..., l-1]
ej. abcd
a: esta en la posicion 0
b: esta en la posicion 1
...
d: esta en la posicion 3

tenemos un conjunto ordenado o lista ordenada C, en donde estan todos los caracteres de nuestra cadena.

entonces una nueva permutacion para un X dado seria
cad = "";
MIENTRAS m varia entre 0 y (longitud cadena -1)
//concatenacion (+)
c = C[ (X mod (n-1)!)/(n-(1+m))! ]
cad = cad + c
// Al conjunto le eliminamos el elemento instertado en cad
C = C - {c}
m = m+1

Gran formula, me tomo 2 dias concluir la solucion haber si la encuentras...
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Algoritmo de Permutaciones

Publicado por rene (2 intervenciones) el 22/07/2010 02:55:42
código en genie del compilador valac

init
var
p="abc"
permut(p.to_utf8(),0)

def permut(a:array of char,l:int)
var
i=0 j=0 n=a.length
c:char
for i=0 to (n-l-1)
if n-l>2
permut(a,l+1)
else
for s in a do stdout.printf("%c",s)
stdout.printf("\n")
c=a[l]
a[l]=a[l+i+1]
a[l+i+1]= c
if l+i==n-1 do for j=l to (n-1) do a[j] =a[j+1]

La variable p es el string que se quiere permutar, utliza una funcion recursiva permuta(
los espacios iniciales son tabs, el archivo tiene la extensión gs
se compila con valac nombre.gs ,se ejecuta en Linux ./nombre
la función p.to_utf8() transforma el string en un arreglo de caracteres
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Algoritmo de Permutaciones

Publicado por rene (2 intervenciones) el 22/07/2010 03:10:29
repito el código anterior porque no se veían los espacios iniciales que son tabs
al compilarlo marcarían error, el código me funcionó en ubuntu instalando valac con synaptic

init
var
p="abc"
permut(p.to_utf8(),0)

def permut(a:array of char,l:int)
var
i=0 j=0 n=a.length
c:char
for i=0 to (n-l-1)
if n-l>2
permut(a,l+1)
else
for s in a do stdout.printf("%c",s)
stdout.printf("\n")
c=a[l]
a[l]=a[l+i+1]
a[l+i+1]= c
if l+i==n-1 do for j=l to (n-1) do a[j] =a[j+1]
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar