Permutaciones

Un pequeño programa en ANSI C que muestra una manera de generar todas las permutaciones de un vector.

Descargar código fuente.


/*
    permutaciones.c
   
    Genera una a una todas las permutaciones de un vector.
*/

#include <stdio.h>

/*
    TAM define la cantidad de elementos del vector.
    Pruebe cambiar este valor, pero no olvide que
    la cantidad de permutaciones será TAM!
*/
#define TAM 4

#if TAM < 1
#error Debe haber al menos 1 elemento.
#endif

/* 
    Carga el vector de prueba con números correlativos a partir de 1
*/
void cargar(int vec[], int tam)
{
    int i;

    for(i = 0; i < tam; i++)
    {
        vec[i] = i+1;
    }
}

/*
    Hace una rotación desplazando los elementos una posición
    hacia el comienzo y colocando el primero en el último lugar.
*/
void rotar(int vec[], int tam)
{
    int i, primero;

    primero = vec[0];

    for(i = 1; i < tam; i++)
    {
        vec[i-1] = vec[i];
    }

    vec[tam-1] = primero;
}

/*
    Genera recursivamente una nueva permutación del vector
    tomando tam elementos a partir de la dirección de inicio.
    Lleva la cuenta mediante un apuntador a la variable externa
    cuenta que se incrementa en cada ejecución.
*/
int permutar(int *inicio, int tam, int *cuenta)
{
    static int fact;

    if(tam > 1)
    {
        if(permutar(inicio + 1, tam - 1, cuenta))
        {
            rotar(inicio, tam);
        }
        fact *= tam;
    }
    else
    {
        (*cuenta)++;
        fact = 1;
    }

    return !(*cuenta % fact);
}

/* Muesta el vector */
void mostrar(int vec[], int tam)
{
    int i;

    for(i = 0; i < tam; i++)
    {
        printf("%3d", vec[i]);
    }

    putchar('\n');
}

int main()
{
    int vec[TAM];
    int cuenta = 0;

    cargar(vec, TAM);

    printf("Elementos:      %3d\n", TAM);
    printf("Estado inicial: ");
    mostrar(vec, TAM);
    putchar('\n');

    do
    {
        printf("%3d:\t", cuenta+1);
        mostrar(vec, TAM);
    } while(!permutar(vec, TAM, &cuenta));

    printf("\nPermutaciones: %3d\n", cuenta);
    printf("Estado final: ");
    mostrar(vec, TAM);

    return 0;
}