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. La siguiente implementación en C ha sido extraida de este artículo (p. 154). A continuació se reproduce la parte 'magica' del algoritmo:

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.
/* invierte el orden del array de enteros P 
 * OJO: el elemento '0' del array P *no* se procesa; y P[N] *sí* cuenta
 */
void reverse (int *P, int N) {
  int i = 1;  
  while ( i < (N+1-i) ) {
    swap(&P[i], &P[N+1-i]);
    i ++;
  }
}

int B(int N, int c) {  
  return ( (N % 2) != 0 ? 1 : c );
}

/* permutaciones en orden lexicografico; cuenta tambien el total 
 * OJO: el elemento '0' del array P *no* se procesa; y P[N] *sí* cuenta
 */
void lexperms (int *P, int N, int *total) {
  
  int i;
  int c[N];
  for (i = N; i > 1; i --) {
    c[i] = 1;
  }
  i = 2;
  
  process(P,N,total);   
  do {
    if (c[i] < i) {
      swap(&P[i],&P[c[i]]);
      reverse(P,i-1); /* inversion parcial! */
      process(P,N,total);
      c[i] ++;
      i = 2;
    } else {
      c[i] = 1;
      i ++;
    }
  } while (i <= N);
}

Puedes descargar un programa de ejemplo que usa la función anterior: perm.c. De nuevo, CUIDADO: los arrays con permutaciones que recibe la funcion "process()" van de P[1] a P[N], y encima están invertidos.



Universidad Autonoma de Madrid, 2007-2008