La búsqueda de la simetría del grupo

Question

Se quiere diseñar un conjunto de preguntas sí/no para la búsqueda rápida de el grupo simétrico. Las preguntas tienen que ser de la forma "¿su permutación mover $a_1$ $b_1$o $a_2$ $b_2$o ... o $a_k$$b_k$?" Dada una permutación aleatoria, se pedirá a todas sus preguntas acerca de que permutación, y su objetivo es saber cuál es la permutación es una vez que usted sabe las respuestas a sus preguntas.

En particular, tenga en cuenta que no se permite tener más tarde las preguntas dependen de las respuestas a las preguntas anteriores. Siempre las mismas preguntas de cualquier permutación aleatoria de obtener.

Aquí está una manera ligeramente diferente a la frase el tipo de pregunta que te permitían hacer. Si representamos los elementos del grupo simétrico de permutación de matrices, a continuación, las preguntas que usted puede pedir implican escoger un (0,1)-matriz y la pregunta de si la permutación aleatoria de la matriz tiene 1 donde elegido matriz tiene un 1 (es decir, si yo aplico la de las componentes Y la función de la matriz y la matriz, obtengo 0 o 1?)

Dos preguntas:

1. Cómo muchas de estas preguntas son necesarias en orden a la búsqueda de $S_n$? Cuánto más grande que $log_2 n!$ es esto?
2. Hay "buenas" estrategias para el diseño de conjuntos de preguntas que se pueden usar para cualquier n? Podemos alcanzar el número mínimo de preguntas para cada n con una sola estrategia?

Answer 1

(La pregunta se actualizó después de esta respuesta y El comentario de abajo fueron escritos)

Si usted pregunta a $p$ preguntas, entonces la cadena de respuestas es una secuencia de $p$ bits, en la mayoría de las $2^p$ respuestas diferentes. Si la cadena de respuestas que se supone identificar una única permutación, entonces usted necesita que $2^p\geq n!$ o, equivalentemente, que el $p\geq\log_2n!$.

Answer 2

Ciertamente, no es difícil obtener una cota superior de a $n\lceil \log_2 n \rceil = O(\log_2 n!)$. Todo lo que necesitas hacer es por separado aprender cada bit de cada valor de la permutación. Esto parece que es sólo aproximadamente la óptima, pero en realidad ya es $(1+o(1))(\log_2 n!)$. (Gracias a t3suji para darse cuenta de esto). Sin embargo, el $o(1)$ plazo sólo decae de forma logarítmica en este algoritmo, así que usted podría preguntar si se podría hacer $(1+O(n^{-\alpha}))(\log_2 n!)$.

Estoy de acuerdo con Michael que parece similar a la asintótica cuestión de la clasificación con las comparaciones. Sin embargo, en la habitual versión de ese problema, se le permite mover elementos con base en una lista incompleta de las comparaciones, que, a continuación, las cantidades de adaptación de las comparaciones. Usted podría llamar a esta nueva pregunta "no adaptativos Cerebro para permutaciones con la matriz de conjeturas". Michael también se sugirió que el problema restringido de permutación conjeturas, que parece ser un problema más difícil para mí.

Answer 3

Esto es probable que sea un problema de difícil solución. Se siente de forma análoga a la determinación del número mínimo de comparaciones necesarias para ordenar n elementos, que parece ser sólo conocido hasta n = 13. En particular, en ambos casos estamos recibiendo información acerca de una permutación de un bit a la vez.

Sin embargo, creo que es sabido que asintóticamente el número de comparaciones necesarias para ordenar n elementos es $(1+o(1)) log_2 (n!)$; no se sorprenda al saber que el mismo es cierto para su problema. Sin embargo, la restricción que más tarde las preguntas no pueden depender de preguntas anteriores hace que las cosas difíciles, porque es difícil pensar en "ortogonal" preguntas.

La llamada de lo desconocido permutación $\sigma$. A continuación, un tipo de pregunta que podría plantearse es "¿su permutación satisfacer $\sigma(k) = \tau(k)$ cualquier $k$", donde $\tau$ es algunos fijos de permutación. En general, la respuesta será "sí" con una probabilidad de aproximadamente 1-1/e. Tal vez una inteligente elección de permutaciones $\tau$ daría lugar a una solución que requieren $C log_2 (n!)$ preguntas, donde $C = 1.0537...$ es el recíproco de la entropía (en bits) de un Bernoulli(1-1/e) de la variable aleatoria.