 Autor
|
Tema: Problema con formula para generar permutaciones (Leído 8,576 veces)
|
Blaster
 Desconectado
Mensajes: 190
|
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. 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!
|
|
|
|
« Última modificación: 26 Diciembre 2013, 14:39 pm por Blaster »
|
En línea
|
|
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
Explica lo que te pide el ejercicio.
Eso ponlo como una cita, no como un code.
|
|
|
|
|
En línea
|
|
|
|
Blaster
Desconectado
Mensajes: 190
|
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  |
|
|
|
« Última modificación: 30 Diciembre 2013, 14:58 pm por Blaster »
|
En línea
|
|
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
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 |
|
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
La fórmula de las permutaciones es:............................. 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
|
|
|
|
|
En línea
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
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.
|
|
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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:Y aplicada al ejemplo que propones es: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: 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.  ¡¡¡¡ Saluditos! ..... !!!!
|
|
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
Efectivamente, lo correcto es lo que ha dicho leosansanDe todas formas, el algoritmo para obtener todas las permutaciones de un conjunto de elementos es muy sencillo:
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: 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: 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! |
|
|
|
|
En línea
|
- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Problema con formula de Excel 2003
Dudas Generales
|
Dannysoft
|
1
|
2,791
|
16 Agosto 2012, 06:32 am
por jvchino
|
|
|
|
Problema al generar Código php para subir archivos a mi FTP
PHP
|
WiseHidden
|
5
|
4,601
|
24 Septiembre 2012, 22:39 pm
por WiseHidden
|
|
|
|
Problema gtx650ti y crosshair ii formula (SOLUCIONADO)
Hardware
|
Root~
|
2
|
2,241
|
7 Enero 2013, 22:45 pm
por Aprendiz-Oscuro
|
|
|
|
fórmula para el tiempo promedio requerido para satisfacer una solicitud.
Dudas Generales
|
Erix
|
0
|
3,148
|
27 Abril 2013, 07:25 am
por Erix
|
|
|
|
problema con formula y aplicación
Java
|
yony86
|
7
|
2,901
|
8 Noviembre 2016, 18:34 pm
por engel lex
|
 |
