2009-07-30 16 views
5

¿Hay una clase de plantilla C++ que implemente operaciones con permutaciones y grupos de permutación? Tal clase tiene que implementar la búsqueda de producto e inversa, multiplicación, etc.¿Hay alguna clase de C++ que implemente operaciones con permutaciones?

+0

En C++ moderno, no usaría una clase para esto. Probablemente usarías múltiples plantillas de funciones. Una plantilla de función por operación que desea admitir, con los rangos de entrada reales con plantilla. – MSalters

+0

La programación funcional no es una opción. La programación orientada a objetos es buena. Realmente necesito una clase de plantilla. –

+2

@MSalters: ¿Cuál es el "rango de entrada" para una función que toma dos permutaciones y devuelve el producto de esas permutaciones? ¿Está sugiriendo que las permutaciones se representan mejor al cliente como pares de iteradores que como objetos opacos? Creo que Alexey busca algo con más conocimiento de la teoría de grupos que std :: next_permutation. –

Respuesta

3

This es lo mejor que he encontrado ... pero está en C, así que tendrás que escribir un contenedor. CodeCogs también le ofrece una biblioteca sobre combinatoria.

-3

STL incluye una función para la permutación en algorithm.h. Aquí hay un ejemplo para eso.

 
int main() { 
    int myints[] = {1,2,3}; 
    cout << "The 3! possible permutations with 3 elements:\n"; 
    sort (myints,myints+3); 
    do { 
    cout << myints[0] << " " << myints[1] <<" " << myints[2] << endl; 
    } while (next_permutation (myints,myints+3)); 
    return 0; 
} 
+2

Por favor, "algoritmo" no "algorithm.h"! – KTC

+1

¿Cómo me ayuda a encontrar la permutación inversa, por ejemplo? –

+0

No es así. Esta función simplemente enumera los miembros del grupo de permutación. No sabe nada sobre la estructura del grupo; solo se basa en los elementos de la matriz de entrada que tiene un orden definido. –

0

No conozco ninguno, pero debería ser lo suficientemente fácil de implementar. Internamente, podría representar la permutación como un vector, p. (1 3 4 2 7 5 6) siendo una permanente de 1-7 enviando 1-> 1, 2-> 3, 3-> 4, 4-> 2 etc. o como un conjunto de ciclos, p. (1) (2 3 4) (5 7 6), e implementar las operaciones en términos de estos. Presumiblemente, el argumento de la plantilla sería el tamaño del grupo de permutación.

Cuestiones relacionadas