Generador de permutaciones en C

Necesito un algoritmo simple de generador de permutaciones que pueda aplicarse en lenguaje C simple.

Permuta sobre números:

Para utilizar cada permutación, debe conectarse a la función de impresión.

#include  #include  /** Read a number, N, from standard input and print the permutations. */ void print(const int *v, const int size) { if (v != 0) { for (int i = 0; i < size; i++) { printf("%4d", v[i] ); } printf("\n"); } } // print void swap(int *v, const int i, const int j) { int t; t = v[i]; v[i] = v[j]; v[j] = t; } void rotateLeft(int *v, const int start, const int n) { int tmp = v[start]; for (int i = start; i < n-1; i++) { v[i] = v[i+1]; } v[n-1] = tmp; } // rotateLeft void permute(int *v, const int start, const int n) { print(v, n); if (start < n) { int i, j; for (i = n-2; i >= start; i--) { for (j = i + 1; j < n; j++) { swap(v, i, j); permute(v, i+1, n); } // for j rotateLeft(v, i, n); } // for i } } // permute void init(int *v, int N) { for (int i = 0; i < N; i++) { v[i] = i+1; } } // init int main() { int *v = (int*) malloc(sizeof(int)*10); init(v, 10); permute(v, 0, 10); free(v); } 

todos

Encontré algoritmos para generar permutaciones en orden lexicográfico de The Art of Computer Programming (TAOCP):

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Generación en orden lexicográfico Hay muchas formas de generar sistemáticamente todas las permutaciones de una secuencia dada [cita requerida]. Un algoritmo clásico, que es a la vez simple y flexible, se basa en encontrar la siguiente permutación en el orden lexicográfico, si existe. Puede manejar valores repetidos, en cuyo caso genera las distintas permutaciones de conjuntos múltiples cada vez. Incluso para las permutaciones ordinarias, es significativamente más eficiente que generar valores para el código de Lehmer en orden lexicográfico (posiblemente utilizando el sistema de números factoriales) y convertirlos en permutaciones. Para usarlo, uno comienza ordenando la secuencia en orden (débilmente creciente) (lo que da su permutación mínima lexicográficamente), y luego repite avanzando a la siguiente permutación siempre que se encuentre uno. El método se remonta a Narayana Pandita en la India del siglo XIV, y se ha vuelto a descubrir con frecuencia desde entonces.

El siguiente algoritmo genera la siguiente permutación lexicográficamente después de una permutación dada. Cambia la permutación dada en el lugar.

  1. Encuentre el índice más grande k tal que a [k]
  2. Encuentre el índice más grande l tal que a [k]
  3. Intercambia una [k] con una [l].
  4. Invierta la secuencia de a [k + 1] hasta e incluyendo el elemento final a [n].

Después del paso 1, uno sabe que todos los elementos estrictamente después de la posición k forman una secuencia que disminuye débilmente, por lo que ninguna permutación de estos elementos hará que avance en orden lexicográfico; para avanzar hay que boost a [k]. El paso 2 encuentra el valor más pequeño a [l] para reemplazar a [k] por, e intercambiarlos en el paso 3 deja la secuencia después de la posición k en un orden ligeramente decreciente. La inversión de esta secuencia en el paso 4 produce su permutación lexicográficamente mínima y el sucesor lexicográfico del estado inicial para toda la secuencia.

Este es un algoritmo clásico encontrado (entre otros lugares) en el TAOCP de Knuth.

Aquí hay un ejemplo que utilicé para un problema de euler de proyecto. Crea todas las permutaciones de una cadena en orden lexicográfico y las imprime en la salida estándar.

 #include int main() { char set[10]="0123456789"; char scratch; int lastpermutation = 0; int i, j, k, l; printf("%s\n",set); while (!lastpermutation) { //find largest j such that set[j] < set[j+1]; if no such j then done j = -1; for (i = 0; i < 10; i++) { if (set[i+1] > set[i]) { j = i; } } if (j == -1) { lastpermutation = 1; } if (!lastpermutation) { for (i = j+1; i < 10; i++) { if (set[i] > set[j]) { l = i; } } scratch = set[j]; set[j] = set[l]; set[l] = scratch; //reverse j+1 to end k = (9-j)/2; // number of pairs to swap for (i = 0; i < k; i++) { scratch = set[j+1+i]; set[j+1+i] = set[9-i]; set[9-i] = scratch; } printf("%s\n",set); } } return 0; } 

Aquí hay una solución recursiva simple para producir todas las permutaciones de un conjunto de caracteres pasados ​​en la línea de comando:

 #include  #include  int perm(const char *src, int len, char *dest, char *destbits, int n) { if (n == len) { printf("%.*s\n", len, dest); return 1; } else { int count = 0; for (int i = 0; i < len; i++) { if (destbits[i] == 0) { destbits[i] = 1; dest[n] = src[i]; count += perm(src, len, dest, destbits, n + 1); destbits[i] = 0; } } return count; } } int main(int argc, char *argv[]) { const char *src = (argc > 1) ? argv[1] : "123456789"; int len = strlen(src); char dest[len], destbits[len]; memset(destbits, 0, sizeof destbits); int total = perm(src, len, dest, destbits, 0); printf("%d combinations\n", total); return 0; }