Problema con formula para generar permutaciones

[Blaster]

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 (bash) [Seleccionar] Expandir


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!

[amchacon]

No se entiende nada, tampoco preguntan nada

[ivancea96]

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

[Blaster]

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  

[dato000]

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

[ivancea96]

La fórmula de las permutaciones es:

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

[leosansan]

La fórmula de las permutaciones es:

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

n!

[ivancea96]

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:

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

[leosansan]

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:

n!/(n-r)!

Y aplicada al ejemplo que propones es:

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 se tienen n elementos y se tomen n a n.Como ejemplo las permutaciones del conjunto {1,2,3] son:

123
132
213
231
312
321

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  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! ..... !!!!

[do-while]

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 [Seleccionar] Expandir



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 [Seleccionar] Expandir


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 [Seleccionar] Expandir


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!