Combinaciones
Hola, tengo una pregunta relacionada con el desarrollo de un juego; ¿Existe algún método o algoritmo que me permita procesar todos los casos posibles?
Es decir, si tengo 5 elementos y quiero procesar todas las posibilidades, tendría 5! , son 80, combinaciones posibles; ¿Hay algún algoritmo que resuelva esto para un numero n de elementos?
Muchas gracias
Es decir, si tengo 5 elementos y quiero procesar todas las posibilidades, tendría 5! , son 80, combinaciones posibles; ¿Hay algún algoritmo que resuelva esto para un numero n de elementos?
Muchas gracias
Respuesta
1
El algoritmo que pongo a continuación genera la siguiente permutación según un orden cíclico, es decir, después de n! Llamadas, se vuelve al mismo vector original. Es un algoritmo que trabaja en "in situ": en el mismo array.
Siguiente-permutacion(a[1..n]: array por referencia) {
1. Encontrar el i más grande que cumpla a<a[i+1].
2. Encontrar el último j>i con a[j]>a.
3. Intercambiar los elementos de las posiciones i y j.
4. Invertir el orden de las posiciones desde la i+1 hasta la n.
}
Este algoritmo es mejorable si se guardan algunos valores estáticamente.
Hay otro modo más rápido pero tengo que buscarlo.
Siguiente-permutacion(a[1..n]: array por referencia) {
1. Encontrar el i más grande que cumpla a<a[i+1].
2. Encontrar el último j>i con a[j]>a.
3. Intercambiar los elementos de las posiciones i y j.
4. Invertir el orden de las posiciones desde la i+1 hasta la n.
}
Este algoritmo es mejorable si se guardan algunos valores estáticamente.
Hay otro modo más rápido pero tengo que buscarlo.