Permutaciones en c++

Buenas.

Antes que nada aclarar que combinaciones y permutaciones no son lo mismo, el que quiera una explicación sobre esto, aquí no la encontrará, ok una permutación (segun la wikipedia) “cada una de las posibles ordenaciones de los elementos de dicho conjunto”.

Por ejemplo:

tiene 6 posibles permutaciones, como sabemos que tiene 6? en breve lo voy a explicar, las cuales son:

detengamonos un poco y veamos lo dicho anteriormente sobre la cantidad de permutaciones, la forma de determinar cuantas permutaciones tiene un conjunto, en nuestro caso nuestro conjunto era (1, 2, 3) es mediante el factorial, hablamos un poco sobre el factorial.

El factorial es el producto de todos los numeros naturales desde n hasta 1, siendo n nuestro numero a determinar el factorial, lo podemos ver de la siguiente manera:

o para los que no esten relacionados con el simbolo de la productoria verlo así:

aca dejo un pequeño snippet de como calcular factorial, me diran que me drogo pero me da miendo usar recursividad y pues el factorial normalmente se calcula de esa forma, pero prefieron hacerlo iterando

int factorial(int n)
{
    int ret = 1;

    for(int i = n; i >= 1; --i)
        ret *= i;

    return ret;
}

bueno ya a grosso modo sabemos lo que es el factorial, vamos con lo que nos compete en este artículo que son las permutaciones, no nos vamos a complicar la vida haciendo esto a mano puesto ya esta implementado en la stl de c++, aunque realmente es bastante sencillo si algún dia que no tenga tanta flojera como hoy lo hago a mano.

El codigo lo que hace es devolver una matriz de enteros, hay que pasarle como parametro el arreglo de enteros donde estan los numeros a permutar, y el tamaño del arreglo como segundo parametro, hay que aclarar que hay que tener la funcion factorial mostrada anteriormente disponible porque se va a usar tanto como internamente para crear la matriz y para liberar la memoria.

Primero hay que tener incluida la libreria correspondiente
[cc lang = "cpp"]#include [/cc]

aca podemos ver el code ya hecho:

[cc lang = "cpp"]int** permutaciones(int* pInts, int n)
{
int m = factorial(n);

int** ret = new int* [m];

for(int i = 0; i < m; i++)
ret[i] = new int[n];

sort(pInts, pInts+n);

for(int h = 0; h < n; ++h)
ret[0][h] = pInts[h];

for(int i = 1; i < m && next_permutation(pInts, pInts+n); i++)
for(int j = 0; j < n; j++)
ret[i][j] = pInts[j];

return ret;
}[/cc]

ojo como ha sido usado memoria dinámica, hay que liberarla, esto queda de parte del programador cuando use la función, forma de liberar la memoria al ser un puntero a punteros se pone a seguir, suponiendo que nuestra matriz, en un derroche de imaginación la llamamos matriz, al arreglo lo llamaremos arreglo y al tamaño tamanho, bueno sigo antes de que empieze a divagar o con mis diarreas verbales

[cc lang = "cpp"]
int** matriz = permutacion(arreglo, tamanho)

/*….*/

for(int i = 0; i < factorial(n); i++)
delete [] matriz[i];

delete [] matriz;
[/cc]

bueno este es un tema muy pero que muy amplio esto es una leve introducción del mismo, ya saben para dudas, correcciones, críticas y amenazas de muerte solo comenten, espero que les sea de utilidad.

• 

Posts Relacionados

• Solución a ¿Cuántas formas? Primero, no importan que caracteres son, con o da la...