Lista de los no-de inmediato-la repetición permutaciones

Question

Antecedentes: estoy tratando de diseñar un ensayo científico (ciencias de la computación tesis doctoral) en los que los participantes responder a 8 preguntas. De hecho, hay sólo 4 preguntas, pero cada uno se le pidió en dos formas diferentes, por lo que hay 4 únicas respuestas correctas, vamos a llamar a, b, c y d. Así que el conjunto de las respuestas correctas serán {a, a, b, b, c, c, d, d}.

El 8 de juicio las preguntas deben aparecer en un orden aleatorio, sin embargo, de la pregunta con la misma respuesta correcta debe aparecer inmediatamente después de la otra. Así por ejemplo, una pregunta con respuesta de un medio de la siguiente pregunta no debe tener también una respuesta.

Me gustaría producir una lista de las permutaciones de {a, a, b, b, c, c, d, d} que no se repiten en este camino. Estoy tratando de escribir un algoritmo para esto, pero estoy teniendo un poco de problemas con las matemáticas. Cualquier ayuda sería muy apreciada.

Alguien podría darme algunos consejos sobre cómo producir esta lista o cómo reducir la lista de 2520 permutaciones de {a, a, b, b, c, c, d, d} para que contenga sólo las permutaciones con mi condición?

Gracias.

Answer 1

Sé que tu pregunta sea una pareja casada asientos problema: $n$ parejas van al cine y, por alguna razón, los cónyuges no quiere sentarse uno al lado del otro.

El número puede ser calculado por medio de la inclusión-exclusión: se calcula el número total de maneras en las ocho respuestas se pueden organizar $8!/2^4$, restar el número en un par pegada $4\times 7!/2^3$, agregar el número donde dos pares están pegadas ${4 \choose 2}\times 6!/2^2$, restar ${4 \choose 3}\times 5!/2^1$ y añadir ${4 \choose 4}\times 4!/2^0$. Esto da un resultado de 864.

Así que en general tiene $$\sum_{i=0}^n (-1)^i {n \choose i} (2n-i)! / 2^{n-i}$$ and in fact the $n=0$ and $n=1$ términos se anulan.

Aunque no sólo puede ser 2520 permutaciones de sus cuatro pares de respuestas, de hecho, hay 40320 permutaciones de las preguntas en total ($2^4$ veces más). De la misma manera hay $2^4$ veces como muchos aceptable permutaciones de las preguntas donde no hay respuestas idénticas están juntos, es decir, 13824 y el término general que se convierte en $$\sum_{i=0 }^n (-2)^i {n \choose i} (2n-i)! $$

OEIS A114938 y A007060 dar más términos, si los necesita. Parece como si para un gran número de pares, sobre el 36,7% de las permutaciones de satisfacer las condiciones requeridas, por lo que una manera fácil de generar uno en particular, en lugar de todos a la vez, se podría tomar una muestra aleatoria de permutación pero si no puede elegir a otro hasta que haya uno que cumple la condición.

Answer 2

En caso de que usted todavía necesita código de Mathematica para resolver su problema - esto debe darle exactamente lo que necesita.

Characters /@ (Select[#, StringFreeQ[#, RegularExpression["aa|bb|cc|dd"]] &] &@ Map[StringJoin, #, 1] &@Permutations[Characters["aabbccdd"]])