¿Cómo generar directamente permutaciones sin fijo puntos?

Question

He leído esto, sin embargo, la fórmula recursiva requiere que la información completa(todos los ciclos con y sin puntos fijos) de la "último paso". Me pregunto si existe un algoritmo que directamente puede generar permutaciones sin puntos fijos?

Por ejemplo, cuando se $n=4$, el resultado es

(1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) 
(1 4 3 2) (1 2)(3 4) (1 3)(2 4) (1 4)(2 3)

algunas aclaraciones

Yo estaba luchando con esta parte: para un determinado $n$, y dada la partición(el número de ciclos y la duración del ciclo), cómo generar todos los posibles, no duplicado ciclos? por ejemplo, dada $n=4$ y dos ciclos de longitud 2, 2, respectivamente, de cómo son (1 2)(3 4) (1 3)(2 4) (1 4)(2 3)generados?

En primer lugar, entiendo que no es un uno-a-uno la asignación entre los "desarreglos", y "permutación ciclo de la representación con todo el ciclo de longitud mayor que uno". Así que la solución es una solución a mi pregunta.

En segundo lugar, sólo quiero generar todos estos ciclos/alteraciones para un determinado n, no uno en concreto, o alguna probabilidad, por ejemplo, dada $n=4$, espero obtener de la colección anterior, o una colección de las alteraciones de la longitud de 4.

En tercer lugar, el único requisito para el método o algoritmo o fórmula es: no generar todas las permutaciones y, a continuación, eliminar los que no se cumple la condición. es decir, genera directamente las respuestas una por una.

Answer 1

Cada permutación tiene una representación como producto de ciclos disjuntos. Con la adecuada consideración de la conmutatividad de los factores, esta representación es única. Dado que la alteración es una permutación sin puntos fijos, es decir, en el que cada uno de distinto ciclo tiene una longitud mayor que uno, todas las alteraciones de $\{1,2,\ldots,n\}$ puede ser construido a partir de las particiones del conjunto de tener piezas de tamaño, al menos, dos.

En efecto, dada una partición, es decir tener $m$ partes de los tamaños de las $k_1+k_2+\ldots+k_m=n$ y cada una de las $k_i\ge2$, no va a ser $\prod_{i=1}^m (k_i-1)! $ correspondiente alteraciones.

Convirtiendo esta observación en explícito algoritmo proporciona una oportunidad para hablar tanto de la generación de particiones de enteros de $n$ y la generación de las particiones del conjunto de $\{1,2,\ldots,n\}$.

1. De entrada entero positivo $n$. Si $n \lt 2$, la salida (sin alteraciones).
2. Generar todas las particiones de enteros de $n$ cuya parte más pequeña es de al menos dos, es decir,: $$k_1+k_2+\ldots+k_m=n$$ where $ k_1\ge k_2\ge \ldots \ge k_m \ge 2$.
3. Para cada entero partición de $n$, generar todo el conjunto de particiones de $\{1,2,\ldots,n\}$ cuyos subconjuntos tienen sus correspondientes tamaños de $k_i$.
4. Para cada partición del conjunto de $\{1,2,\ldots,n\}$, de generar todas las discontinuo cíclico descomposiciones donde los ciclos de disponer de las piezas de la partición del conjunto como de sus subyacentes distintos conjuntos.
5. La salida de una permutación (trastorno).

Cada paso entre el primero y el quinto se puede lograr en al menos uno y posiblemente en varias maneras. Ya que cada paso depende de los resultados del paso anterior, se generan las salidas como las hojas de un árbol de dependiente de decisiones. A la salida de todos los posibles alteraciones requiere de retroceso a través de este árbol de decisiones, es decir, cuando todas las posibilidades para un determinado paso se agotan, el control pasa al paso anterior para continuar de generación en generación.

Para hacer: Notas sobre la aplicación de medidas 2,3,4,5

Answer 2

Aquí está un algoritmo en pseudocódigo

("::" es su contra, "\" es el operador de la diferencia de set, y "++" es el operador de concatenación de la lista). Básicamente es una modificación del creador de permutación recurrente que omite los puntos fijos.