Generación de asientos planes - número máximo de órdenes con diferentes adyacencias

Question

Antecedentes:

Por lo que la escuela que trabajo tiene una política que tratamos de sentar a los niños junto a tantos otros niños como sea posible durante todo el año académico. Esto significa rejigging el plano de asientos tan a menudo como usted puede ser molestado.

Con un decentish comprensión de VBA, pensé que había que escribir una macro para encargarse de esto para mí, pero me he topado con un inconveniente.

El algoritmo básico es la reorganización de la lista, a continuación, transcribimos que para un plano de asientos en forma predeterminada. La esperanza es la reorganización de la lista de tal manera que no hay dos estudiantes que están al lado de los que fueron antes.

Pero mi problema es que no hay manera sencilla de caracterizar estos baraja.

Matemáticas

Así que supongamos que tenemos una lista ordenada de n elementos (posiblemente será más fácil considerar como lista cíclica, de modo que n es adyacente a 1), ¿cómo se puede generar de forma fiable el número máximo de reorderings de la lista en la que no hay dos reorderings compartir pares adyacentes?

Una clara estrategia podría ser un paseo aleatorio en $S_n$, pero sin saber el número máximo esta lista podría continuar eternamente buscando un reordenamiento que no estaba allí. De manera natural a una pregunta complementaria es: ¿cuál es el número máximo de tales reorderings?

En su defecto, lo que es una manera confiable de decisiones (posiblemente el óptimo número de 'mezcla' reorderings?

Hasta ahora he experimentado con Faro baraja (que no garantizan la mezcla en virtud de su composición), grupos de invertible elementos en $\mathbb{Z}_n^\times$ (grupo multiplicativo de los números enteros modulo n - que parecen muy escasas en sólo ofreciendo $ \phi(n)$/2 reorderings), y han jugado con algunos paseo aleatorio código, todo fue en vano.

Estoy seguro de que esto es sólo un reflejo de mi ignorancia de combinatoria - que la respuesta va a llegar a ser una fracción con un par de factoriales, o que es un famoso problema o alguna de esas. Pero estoy perplejo.

Cualquier ayuda que usted podría dar sería ace. Gracias!

Answer 1

Para una lista cíclica de lo que efectivamente está pidiendo es un Hamilton Descomposición del grafo completo (cada ciclo Hamiltoniano corresponde a un solo día de asientos, y el "no hay dos sentados juntos dos veces" condición es equivalente a ningún borde que aparece en dos ciclos). La construcción de estos fue encontrado por Walecki en el siglo 19, aunque estoy teniendo problemas para encontrar una buena referencia disponible para la construcción real.

La sección $3$ de este papel de David Lucio otorga a la construcción de $n$ impar, que es quizás más fácil visualizar a través del dibujo en la página 118 de Brett Stevens' "Anti-Oberwolfach Solución" de papel (el enlace es a una búsqueda de Libros de Google vista previa, espero que la página en cuestión es visible). Alspach, Bermond, y Sotteau de papel de la "Descomposición en Ciclos I: Hamiltonianos Descomposiciones" describe la construcción en general (ídem en la búsqueda de Libros de Google vista previa).

La construcción de $n=2k+1$ impar parece que funciona más o menos como sigue. Dado que una persona $a$$1$$n$, definir un "zig-zag de partida en $a$" a ser la secuencia $$a,a+1,a-1,a+2,a-2,\dots,a+(k-1),a-(k-1),a+k$$ donde todas las operaciones se toman modulo $2k$. Un zig-zag contiene cada número entre el$1$$2k$, y podemos formar un ciclo Hamiltoniano, conectando a $2k+1$ a ambos extremos. Haciendo esto para cada uno de los zig-zag de $a=1$ $a=k$da Walecki de la descomposición.

Answer 2

Supongo que tu escuela no tiene del Rey Arturo, la Mesa Redonda, por lo que no están realmente en una cadena larga.
Son en pares? Si usted tiene $N$ mesas, cada una se encuentra a 2 estudiantes, usted puede hacer esto:
(1) el Estudiante 1 se encuentra en el lado izquierdo de la Tabla 1 para siempre.
Cada vez que se mueven los estudiantes,
(a) todo el mundo en la mano izquierda se mueve hacia arriba de una mesa,
(b) todo el mundo en la mano derecha se mueve hacia abajo una tabla
(c) El lado izquierdo del estudiante en la Tabla $N$ se mueve al lado derecho de la Tabla de $N$
(d) la mano derecha de La estudiante en la Tabla 1 se mueve a la parte izquierda de la Tabla 2.
Usted puede disfrazar obviamente, va a las $m^{th}$ posición en lugar de la posición siguiente. Tiene la desventaja de que la gente en el frente y detrás de usted permanece el mismo.
Si usted pone las tablas en el orden (no de la Tabla de $k$ frente de la Tabla de $k+1$, usted podría ser capaz de hacer la gente en el frente y detrás de cambiar regularmente. No estoy seguro de cómo hacerlo. Si $N+1$ es primo, usted puede encontrar un generador de $g$ $\mathbb{Z}_{N+1}^{\times}$ y el fin de las mesas de acuerdo a los poderes de la $g$.
Que sólo deja a la gente en el siguiente pasillo; creo que depende de cómo muchos de los pasillos.