Permutaciones en C

Un permutación es una de las posibles configuraciones de un conjunto de n elementos, en la que cada elemento aparece una vez. Para un conjunto de n elemento , hay n! permutaciones. Ej. para el conjunto 123 las permutaciones posibles son 3! = 6. Estas son 123, 132, 213, 231, 312 y 321.

La siguiente tabla muestra el tiempo de computación en función del tamaño n de conjunto. (1 microsegundo por operación)

N	N!	Tiempo
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800	3 segundos
11	39916800	40 segundos
12	479001600	8 minutos
13	6227020800	2 horas
14	87178291200	1 dia
15	1307674368000	2 semanas
16	20922789888000	8 meses
17	355689428096000	10 años

En la literatura exiten multitud de algoritmos para realizar permutaciones. Un buen resumen se puede encontrar en Permutations Generation Methods de R. Sedgewick, ACM Computing Surveys, Vol. 9, No. 2, Junio 1977. Las siguientes implementaciones en C han sido extraidas del anterior artículo.

/* Donde P es un puntero a un array de N enteros
    Esta función implementa la versión no recursiva del primer algoritmo descrito en el apartado 1 del mencionado artículo
*/
void
permutations(int * P, int N);

La función está implementada suponiendo que el primer elemento está en la posición 1 del array, en vez de la posición 0, como es habitual en C. De este modo, al definir el array que se le va suministrar a la función, hay que tener en cuenta que el elemento en la posición 0 no se utiliza en las permutaciones.

#include <stdio.h>

#define true 1
#define false 0

/* Esta función se llama cada vez que se obtiene una permutación.
   Se ha definido que se imprima la permutación.
   Su contenido se puede modificar en función del problema que se desee resolver
*/
void process(int * P, int N) {

  int i;
 
  for (i = 1; i <= N; i ++) {
    printf("%d ", P[i]);
  }
  printf("\n");
}

/* Esta función intercambia dos posiciones del array */
void swap (int * x, int * y) {
 
    int temp;
   
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Necesario definir esta función para que el algoritmo funcione (ver artículo para detalles) */
int B(int N, int c) {
 
  return ( (N % 2) != 0 ? 1 : c );
}

void permutations(int * P, int N) {
 
  int c[N];
  int i;
 
  for (i = N; i > 1; i --) {
    c[i] = 1;
  }
  process(P,N);
  do {
    if  (c[i] < i) {
      swap(&P[B(N,c[i])], &P[i]);
      process(P,N);
      c[i] = c[i] + 1;
      i = 2;
    } else {
      c[i] = 1;
      i ++;
    }
  } while (i <= N);
}

int main() {

  int P[4] = {0,1,2,3}; /* El primer elemento no se utiliza por lo que
                             las permutaciones resultantes serán 123, 132, 213, 231, 312 y 321 */

  permutations(P,3);
  return 0;
}

Si se desea que las permutaciones obtenidas sigan un orden lexicográfico se puede emplear la siguiente función en vez de permutations.

/* Donde P es un puntero a un array de N enteros
    Esta función implementa el Algoritmo 8 (Ord-Smith) p. 154 del citado artículo
    Llama a la función process por cada permutación obtenida en orden lexicográfico
    Necesita de la función reverse, la cual invierte el orden del conjunto
*/
void
lexperms(int * P, int N);

void lexperms (int * P, int N) {
 
  int i;
  int c[N];
 
  for (i = N; i > 1; i --) {
    c[i] = 1;
  }
  i = 2;
  process(P,N);
  do {
    if (c[i] < i) {
      swap(&P[i],&P[c[i]]);
      reverse(P,i-1);
      c[i] ++;
      i = 2;
      process(P,N);
    } else {
      c[i] = 1;
      i ++;
    }
  } while (i <= N);
}

/* invierte el orden del array de enteros P */
void reverse (int * P, int N) {
 int i = 1;
 
 while ( i < (N+1-i) ) {
  swap(&P[i], &P[N+1-i]);
  i ++;
 }
}