Listado permutaciones distintas bajo simetría dada en Mathematica

Question

cross-post de desbordamiento de pila

Tengo una lista de números como {2,1,1,0} y me gustaría lista de todas las permutaciones de esa lista que no son equivalentes, cuenta con el grupo de simetría. Así por ejemplo, si se trataba de un diedro grupo de orden 4, el resultado sería {{2, 1, 1, 0}, {2, 1, 0, 1}}. Es allí una manera práctica de hacer esto cuando la lista es demasiado grande para generar todas las permutaciones?

Mathematica 8 parece tener un par de grupo de teoría de funciones, pero no tengo ninguna teoría del grupo de fondo, por lo que los punteros son apreciados.

Answer 1

Para hacer esto en (el gratuito, de código abierto, por grupo de teoría de software) GAP, puedes usar:

g := Group( (1,2)(3,4), (1,3)(2,4), (1,2,3,4) );;
d := PermutationsList( [2,1,1,0] );;
o := OrbitsDomain( g, d, Permuted );;
r := List( o, orbit -> Reversed( AsSet( orbit ) )[1] );

El primer comando define un diedro grupo (actuando en los vértices de un cuadrado). El segundo comando define el dominio en el que el grupo va a actuar: el conjunto de todas las permutaciones de la lista [2,1,1,0]. Esta lista se construye en la memoria, así que esto limita el tamaño de la lista. Se puede calcular el tamaño de la lista con:

NrPermutationsList([2,1,1,0]);

y buscar un método diferente si la lista es demasiado larga (hasta diez mil va a ser muy rápida, hasta un millón va a estar bien, después de diez o veinte millones tendrás que intentar algo más). El tercer comando ordena el dominio en "órbitas", los conjuntos de equivalente de permutaciones, con el grupo que actúa en el dominio a través de la función "Permutada" que permutes los índices de una lista. El cuarto comando pide la órbita de representantes.

Si g es pequeña en comparación a d, entonces usted está atascado. Esto es simplemente difícil que sea el problema. Si g es bastante grande en comparación con d puede evitar la computación d explícitamente, mediante una transversal de un overgroup de g en el grupo simétrico.

Sin embargo, la prueba esta versión primera. Si se llega a un ejemplo que no funciona, post un grupo específico y la lista y la voy a describir cómo los trabajos transversales (a menudo va a ser más lento, más eficientes en el uso de la memoria).

---

Para trabajar más específicamente con el problema, aquí están algunos BRECHA de comandos. Para muchos particiones, la BRECHA de toma demasiado tiempo (entonces, la memoria de la eficiencia no es el problema). Para obtener un azar de la partición puede utilizar:

x:=Random(Partitions(16));;
Append(x,ListWithIdenticalEntries(16-Size(x),0));;
x; NrPermutationsList(x);

Voy a tomar:

x := [ 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0 ];

Ahora, la construcción del grupo de simetría del hipercubo, el conjunto de las permutaciones de la partición, de las órbitas, y la órbita de los representantes como antes:

g := WreathProductProductAction(SymmetricGroup(2),SymmetricGroup(4));;
d := PermutationsList( x );;
o := OrbitsDomain( g, d, Permuted );;
r := List( o, orbit -> Reversed( AsSet( orbit ) )[1] );;
Size( r );

Después de aproximadamente un minuto, se debe imprimir 1292. Para 16 = 1+1+2+3+4+5 se ha ejecutado por un día o así, y todavía no está acabado. No hay problemas con el uso de la memoria, es sólo tamizar a través de 3 millones de ordenamientos. Así, no es práctico para todas las particiones, pero para muchos se van a funcionar bien.