Primera vez que voy a describir lo que creo que hace de este un problema difícil y, a continuación, dar un algoritmo que reduce significativamente el número de permutaciones usted tiene que manejar, que aunque no es de uno por cada órbita.
El problema puede ser visto como la búsqueda de todas las clases de equivalencia de los Jóvenes de cuadros bajo dos diferentes tipos de operaciones. Por un lado, podemos permutar las filas de igual longitud y cíclicamente permutar las entradas en una fila; una clase de equivalencia en virtud de estas operaciones corresponde a una permutación. Por otro lado, podemos permutar los números en las casillas de acuerdo a los elementos de la $C_\pi$, la cual es generada por las permutaciones de los ciclos de $\pi$ y cíclico de las permutaciones de los elementos de un ciclo de $\pi$; una clase de equivalencia en virtud de estas operaciones corresponde a una órbita en virtud de la conjugación por $C_\pi$.
Podemos ver estos dos tipos de operaciones, como la simetría de operaciones de dos cuadros: uno para la permutación de ser construido y uno para $\pi$. Lo que hace que el problema sea difícil es que estos dos tipos de operaciones de interactuar en una forma complicada. Si sólo tenía que lidiar con uno de ellos en un momento, fácilmente podríamos definir un canónica representante de cada clase de equivalencia utilizando las permutaciones para exigir la adecuada ordenación de las condiciones; un algoritmo eficiente sería entonces consiste en el llenado de los cuadros uno por uno, en cada paso sólo tratando de salir de las posibilidades que son compatibles con el canonicity condiciones.
No he sido capaz de encontrar una forma canónica para ambos tipos de operaciones, a la vez que sería sencillo para comprobar si está parcialmente construido permutación todavía puede terminar como una forma canónica. La mejor que pude hacer fue poner en canonicity plenamente de uno de los tipos y parcialmente para el otro; sin embargo, esto ya se reduce sustancialmente el número de permutaciones que deben ser generados.
Esto plantea la cuestión de cuál de los tipos de operaciones canonicity debe ser aplicada en su totalidad. Si es aplicada en su totalidad para el primer tipo, correspondientes a las simetrías del tableau de la permutación que se genera, entonces generamos cada permutación sólo una vez, pero podemos generar varios representantes de la órbita. Si es aplicada en su totalidad para el segundo tipo, correspondientes a las simetrías del tableau para $\pi$, entonces podemos generar sólo un representante de cada órbita, pero nos puede generar varias veces.
En el primer caso, tenemos que agregar un paso en la final que canonicalizes las permutaciones con respecto al segundo tipo de operaciones para asegurarnos de mantener sólo un representante de cada órbita; mientras que en el segundo caso sólo tenemos que comprobar si ya hemos producido un dado de permutación. Ya que es un poco más fácil, voy a describir un algoritmo que utiliza la segunda opción (completo canonicity para el segundo tipo de operaciones); una vez que hemos visto esto, va a ser relativamente sencillo para formular el otro si así lo prefieren. (Cual de estas dos opciones elimina más de redundancia probablemente dependerá $\pi$, posiblemente en una forma complicada, ya que podría ser una pregunta mejor decidió por pruebas empíricas que opción sería la más eficiente para la aplicación.)
Encontrar la estructura del ciclo de $\pi$, y de considerar su Joven diagrama de $Y_\pi$. Bucle a través de todas las particiones de $n$ (por ejemplo, la Sección 7.2.1.4 de El Arte de la Programación de la Computadora muestra cómo hacerlo), y para cada una de las particiones $p$, considerar la correspondiente Jóvenes diagrama de $Y_p$. Queremos asignar las cajas de $Y_p$ a las cajas de $Y_\pi$ en todas las formas posibles. Para hacer cumplir canonicity con respecto a $Y_\pi$, podemos asignar las cajas de $Y_p$ uno por uno, que atraviesa $Y_p$ fila por fila de arriba a abajo y de izquierda a derecha; en cada paso, se puede asignar el siguiente cuadro de $a$ $Y_p$ a un cuadro de $b$ $Y_\pi$ sólo si el primer cuadro de la fila que contenga $b$ ya ha sido usado o si $b$ es el primer cuadro en su fila y todos los primeros cuadros en las filas de igual longitud por encima de ella ya han sido usadas. Podemos recorrer todas las posibilidades que cumplen esta condición y para cada una de tales posibilidad de $b$ asignamos $a$ $b$y hacer una llamada recursiva para asignar el siguiente cuadro. Esto asegura que generamos exactamente uno de todas las tareas relacionadas con la simetría de las operaciones de $Y_\pi$, es decir, generamos un solo representante por cada órbita.
Ahora queremos intentar generar cada uno de los representantes cuantas veces como sea posible; es decir, queremos hacer valer canonicity con respecto a $Y_p$ tanto como sea posible. Considere la posibilidad de la cesión de toda una fila $r$$Y_p$. Ya podemos cíclicamente permutar las casillas de la fila, podemos transformar algunas de las tareas en cada uno de los otros. Al principio uno podría pensar (y mi primera respuesta incorrecta basaba en la suposición) que siempre nos sólo hay que considerar la asignación de donde el primer cuadro de $r$ es asignado al menos un cuadro (de acuerdo a un orden fijo $\omega$)$Y_\pi$, ya que de lo contrario podemos cíclicamente permutar $r$ a que sea así. Sin embargo, esto no es del todo cierto, ya que este puede estar en conflicto con la canonicity condiciones para $Y_\pi$. Por ejemplo, si $r$ tiene tres cajas de $r_1, r_2, r_3$ y se le asignó a $r_1$ para el primer cuadro de $s_1$ de la fila $s$ en $Y_\pi$, $r_2$ para algunos la caja menor en $\omega$, y, a continuación, $r_3$ para el segundo cuadro de $s_2$$s$, no podemos cíclicamente permutar las cajas de $r$ tal que $r_1$ toma el lugar de $r_2$ (como debe ser), ya que harían $r_2$ tomar el lugar de $r_3$ $r_3$ tomar el lugar de $r_1$, lo que resulta en una asignación de $r_3$$s_1$$r_2$%#%, lo cual viola la canonicity condiciones para $s_2$.
Sin embargo, como se puede ver en el ejemplo, este problema sólo puede producirse si se asigna cajas de $Y_\pi$ a las cajas de $Y_p$ que debe ser llenado en un determinado orden entre sí, es decir, a la primera casilla en una fila y otra caja en la fila, o a las dos primeras casillas de las filas de igual longitud. Para un gran $Y_\pi$, la mayoría de los posibles asignaciones no va a conducir a una colisión, y en estos casos que realmente sólo tiene que tratar de la asignación que garantice canonicity con respecto a $n$.
Para aplicar esto en el algoritmo anterior, siempre que se le asigne la última casilla de la fila $Y_p$$r$, menos de cuadro de $Y_p$ (de acuerdo a $b$) de las cajas que las cajas de $\omega$ están asignados y compruebe si hay alguna permutación cíclica de las cajas de $r$ que provoca un cuadro de $r$ más a la izquierda para ser asignado a $r$ y que no vulneran la canonicity condiciones para $b$. Si es así, eso significa que vamos a llegar a que permutan asignación en alguna otra etapa del algoritmo, por lo que podemos saltar ahora. Si no la hay (en particular, si el primer cuadro de $Y_\pi$ ya está asignado a $r$), el uso de la inalterado asignación.
Esta se ocupa de las permutaciones cíclicas de las filas de $b$. Podemos lidiar con las permutaciones de filas de $Y_p$ de igual longitud, en una manera similar. Para ello, siempre que se le asigne la última casilla de la fila $Y_p$$r$, después de comprobar que la asignación no debe ser omitido porque de una permutación cíclica de $Y_p$ como se describió anteriormente, compruebe si $r$ tiene otras líneas de igual longitud por encima de ella. Si es así, compruebe si el primer cuadro de $r$ es asignado a un menor (cuadro de acuerdo a $r$) de todas las otras primeras casillas de las filas de $\omega$ de igual longitud. Si es así, utilice la asignación. Si no, compruebe si puede intercambiar $Y_p$ con cualquier fila de arriba es de igual longitud, cuyo primer cuadro se asigna a un menor cuadro de la primera caja de $r$ sin violar la canonicity condiciones para $r$. Si es así, omita la asignación, ya que vamos a llegar con las filas cambiadas en otra etapa del algoritmo. Si no, utilice el inalterada la asignación.
Queda por describir qué hacer cuando has llegado a la última etapa de la recursividad y asignó correctamente el último cuadro de $Y_\pi$ ("correctamente" lo que significa que ha pasado la saltarse las pruebas y ahora tendría que hacer una llamada recursiva para asignar el siguiente cuadro si hay uno). Ahora tienes una cesión completa de las cajas de $Y_p$ a los de $Y_p$ que cumple la canonicity condiciones para $Y_\pi$ y puede producir un nuevo representante. Para la construcción de ese representante, el uso de algunos fijos Jóvenes tableau $Y_\pi$ correspondiente a $T_\pi$ (cualquiera de los otros equivalentes va a hacer, pero debe ser la misma a lo largo) y rellenar las casillas de $\pi$ con los números que las cajas están asignados a en $Y_p$ contienen en $Y_\pi$ (que tiene forma de $T_\pi$.) A continuación, lea la permutación representado por la resultante de los Jóvenes de tableau $Y_\pi$ (que tiene forma de $T_p$), comprobar si se ha generado antes, y si no, añadirlo al conjunto de representantes.
Espero que a) no he hecho ningún injustificado de los supuestos de este tiempo y b) he, al menos, algo sucedió en la descripción del algoritmo de forma que se puedan implementar. Déjeme saber si usted estaría interesado en una implementación en Java.
