Imprimir Página - Problema con formula para generar permutaciones

Título: Problema con formula para generar permutaciones
Publicado por: Blaster en 26 Diciembre 2013, 14:34 pm

Hola a todos

Llevo horas tratando de formular una posible solucion a este enunciado que
encontre por la web, por favor alguien puede darme una idea de como seria la
solucion.

Código

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 
]

Saludos!

Título: Re: Problema con formula para generar permutaciones
Publicado por: amchacon en 26 Diciembre 2013, 15:47 pm

No se entiende nada, tampoco preguntan nada :huh:

Título: Re: Problema con formula para generar permutaciones
Publicado por: ivancea96 en 26 Diciembre 2013, 15:58 pm

Explica lo que te pide el ejercicio.
Eso ponlo como una cita, no como un code.

Título: Re: Problema con formula para generar permutaciones
Publicado por: Blaster en 30 Diciembre 2013, 14:55 pm

Pasa que esta linea (X mod (n-1)!)/(n-(1+m))! se trata de una
formula, que implementandola de la manera correcta en algun lenguaje; podrias
conseguir con ella todas las permutaciones de un conjunto de elementos. Esto lo saque de un foro donde un usuario lo posteo diciendo que le tomo dos dias encontrar la de escribirla en C, quise contactar con este usuario pero este ya no frecuenta el foro.

Saludos ;D

Título: Re: Problema con formula para generar permutaciones
Publicado por: dato000 en 30 Diciembre 2013, 14:59 pm

pues eso parece más python...iria mejor en el foro de scripting :silbar: :silbar:

Título: Re: Problema con formula para generar permutaciones
Publicado por: ivancea96 en 30 Diciembre 2013, 15:04 pm

La fórmula de las permutaciones es:

Citar

n!/((n-r)!)

Donde N es el número de elementos, y R el número de elementos cogidos para cada permutación.
Esta fórmula da resultados cuando NO se repiten los elementos, e IMPORTA el orden.
Por si acaso decirte, que en C/C++ no existe la función factorial (!) por si sola. Quizás en la librería Maths encuentres algo, o sinó haces la función a mano.

4! = 4*3*2*1
2! = 2*1
(El 1 se puede omitir, ya que no aporta nada)
1! = 1
0! = 1

Título: Re: Problema con formula para generar permutaciones
Publicado por: leosansan en 30 Diciembre 2013, 15:36 pm

Cita de: ivancea96 en 30 Diciembre 2013, 15:04 pm

La fórmula de las permutaciones es:

Citar

n!/(n-r)!)

.............................

Perdona pero no. Esa es la fórmula de las variaciones sin repetición de n elementos tomados r a r.

La de las permutaciones sin repetición es simplemente

Citar

Título: Re: Problema con formula para generar permutaciones
Publicado por: ivancea96 en 30 Diciembre 2013, 16:49 pm

En un array de 3 elementos {a, b, c}.
Cuantas formas hay de coger elementos de 2 en 2?

a,b / a,c / b,c / b,a / c,a / c,b

(3*2)/(3-2)! = 6
-----------------------------------
De 1 en 1:

a / b / c

(3*2)/(3-1)! = 3

-----------------------------------

De 3 en 3:

a,b,c / a,c,b / b,a,c / b,c,a / c,a,b / c,b,a

(3*2)/(3-3)! = 6

-----------------------------------------------

Además de lo dicho antes, Leosansan, ahí tienes un ejemplo sencillo.

Repito:

Cita de: ivancea96 en 30 Diciembre 2013, 15:04 pm

Esta fórmula da resultados cuando NO se repiten los elementos, e IMPORTA el orden.

Título: Re: Problema con formula para generar permutaciones
Publicado por: leosansan en 30 Diciembre 2013, 19:43 pm

Siento contradecirte, amigo ivancea96 pero tienes un error de concepto básico. Si tienes tres elementos y los vas a tomar de 2 en 2, sin repetir e importando el orden -si no importara serían combinaciones- son variaciones y su fórmula es:

Citar

n!/(n-r)!

Y aplicada al ejemplo que propones es:

Citar

3!/(3-2)!=3!=6

Curioso, justo lo que te sale a tí, como dicen sonó la flauta ¿Dónde está tu error?. Es conceptual, en las permutaciones (http://es.wikipedia.org/wiki/Permutaci%C3%B3n)se tienen n elementos y se tomen n a n.Como ejemplo las permutaciones del conjunto {1,2,3] son:

Citar

123
132
213
231
312
321

Cita de: ivancea96 en 30 Diciembre 2013, 16:49 pm

En un array de 3 elementos {a, b, c}.
Cuantas formas hay de coger elementos de 2 en 2?

a,b / a,c / b,c / b,a / c,a / c,b

(3*2)/(3-2)! = 6
-----------------------------------

¿Te das cuenta?. No estas tomando los tres elementos por tanto no son permutaciones, sino variaciones y la fórmula que aplicas es la de variaciones.

Resumiendo, y a lo simple:

* permutaciones de n elementos: se toman n a n e importa el orden.

* variaciones de n elementos tomados r a r e importa el orden.

*combinaciones de n elementos tomados r a r y no importa el orden.

Aunque hay mucha información en la red esta (http://sauce.pntic.mec.es/~jpeo0002/Archivos/PDF/T01.pdf) referencia no está mal.

Luego estan con repetición, pero eso no viene al caso ahora mismo.

Espero que este rollito ta aclare las ideas. ;) ;) ;)

;-) ;-) Felices Navidades y Próspero Año Nuevo. ;-) ;-)

¡¡¡¡ Saluditos! ..... !!!!

(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

Título: Re: Problema con formula para generar permutaciones
Publicado por: do-while en 2 Enero 2014, 19:01 pm

Efectivamente, lo correcto es lo que ha dicho leosansan

De todas formas, el algoritmo para obtener todas las permutaciones de un conjunto de elementos es muy sencillo:

Código:


procedimiento permutaciones(lista_permutaciones, conjunto_datos, numero_datos, elementos_fijados)
{
    vector estatico permutacion(numeros_datos);

    si numero_datos == 0
        lista_permutaciones.añadir(permutacion);
        volver;
    fin si

    para i desde 0 hasta numero_datos
        si i != 0
            intercambiar(conjunto_datos(i),conjunto_datos(0));
        fin si

        permutacion(elementos_fijados) = conjunto_datos(0)

        permutaciones(lista_permutaciones, conjunto_datos(elementos_fijados..numero_datos - 1), numero_datos - 1, elementos_fijados + 1);

        si i != 0
            intercambiar(conjunto_datos(i),conjunto_datos(0));
        fin si
    fin para
}

Donde numero_datos, es el numero de datos que hay en conjunto_datos, y elementos_fijados indica cuantos elementos se han puesto ya en la permutación que se esta calculando. Una llamada seria por ejemplo:

Código:

permutaciones(lista,{a,b,c},3,0);

Ya que {a,b,c} tiene 3 elementos, y al no haber empezado a ejecutar el algoritmo todavía no se ha fijado ningún elemento.

Si hacemos la traza comprobaremos que efectivamente el algoritmo calcula todas las permutaciones posibles de los elementos a,b y c:

Código:

lista_permutaciones: vacia
conjunto_datos: {a,b,c}
numero_datos = 3
elementos_fijados = 0

numero_datos != 0
|-> i = 0
  |->permutacion(0) =conjunto_datos(0) = a
  |-> permutacinoes(lista_permutaciones,{b,c},3 - 1 , 1)
    |-> 3 - 1 = 2 != 0
      |-> i = 0
      | |->permutacion(1) = conjunto_datos(0) = b
      | |->permutaciones(lista_permutaciones,{c},2 - 1 , 2)
      |   |->2 - 1 = 1 != 0
      |     |-> i = 0
      |     | |->permutacion(2) = conjunto_datos(0) = c
      |     | |->permutaciones(lista_permutaciones,{},1 - 1, 3)
      |     |   |->1-1 == 0
      |     |     |-> lista.añadir(permutacion = {a,b,c})
      |     |     |->volver
      |     |-> i = 1 == numero_elementos ->fin para -> volver
      |-> i = 1
      | |-> 1 != 0
      | |-> intercambiar(conjunto_datos(0) , conjunto_datos(1)) -> conjunto_datos = {c,b}
      | |-> permutacion(1) = conjunto_datos(0) = c
      | |->permutaciones(lista_permutaciones,{b},2 - 1 , 2)
      |   |->2 - 1 = 1 != 0
      |     |-> i = 0
      |     | |->permutacion(2) = conjunto_datos(0) = b
      |     | |->permutaciones(lista_permutaciones,{},2 - 1, 3)
      |     |   |->1-1 == 0
      |     |     |-> lista.añadir(permutacion = {a,c,b})
      |     |     |->volver
      |     |-> i = 1 == numero_elementos ->fin para -> volver
      | |->intercambiar(conjunto_datos(0),conjunto_datos(1)) -> conjunto_datos = {b,c}
      |
      |-> i = 2 == numero_datos -> volver
i = 1 != 0
  |-> intercambiar(conjunto_datos(0),conjunto_datos(1) -> conjunto_datos = {b,a,c}
  |-> permutacion(0) = conjunto_datos(0) = b
  y continuamos...

¡Saludos!

Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Blaster en 26 Diciembre 2013, 14:34 pm