¿Existe un algoritmo eficiente para encontrar la i-ésima disposición?

9

Aquí está el trasfondo de esta pregunta. Amigos y yo estábamos jugando un juego en el que todos necesitan darle un regalo a otra gente. Para determinar quién debe dar un regalo a quién, decidimos sortear. Pero el problema es que alguien podría terminar dándose regalos, lo cual no es divertido. Puede ver que el número esperado de personas tan desafortunadas es 1, por lo que esto sucede con bastante frecuencia.

Para este propósito, querida disposición parece ser un gran ajuste. Si puedo generar un rango estimado, entonces puedo elegir uno y usarlo para decidir quién da a quién obsequios.

La generación aleatoria de queridos arreglos podría hacerse con el método de Las Vegas. Pero el problema es que solo ha esperado un tiempo de ejecución polinómico. Así que llegué a este problema de encontrar mi querida disposición. Si puedo elegir aleatoriamente una i en [1, D_n], y usar algún algoritmo de tiempo polinómico en el peor de los casos (eficiente) para obtener el i-ésimo rango, entonces está hecho.

permutations Santa Zhang
fuente
1
¿Podría explicar la motivación de la pregunta? es decir, ¿por qué estás interesado en esta pregunta?
Kaveh
2
Quizás quieras jugar al secreto de santa y no estás dispuesto a correr ningún riesgo :)
Lev Reyzin
¿Podría agregar una línea sobre lo que quiere decir con dearrangement?
Vijay D

Respuestas:

9

En realidad, esta podría ser una buena pregunta, pero está mal formulada en su forma actual. Los algoritmos bien conocidos para generar alteraciones aleatorias tienen un tiempo lineal esperado, pero tal vez sea un problema abierto encontrar un algoritmo de tiempo polinómico en el peor de los casos.

Ver por ejemplo: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (y diapositivas: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )

didest
fuente
Esta parece ser la respuesta correcta para mí.
Suresh Venkat
10
¿La recurrencia! N = (n − 1) (! (N − 1) +! (N − 2)) descrita en en.wikipedia.org/wiki/Derangement conduce inmediatamente a un algoritmo polinomial para el peor de los casos al azar ¿Generacion?
David Eppstein
Sí, tiene usted razón. Estaba pensando que hay una pequeña trampa porque tienes que poder generar números aleatorios en subconjuntos arbitrarios de {1, ..., n} en el peor de los casos, pero eso es fácil de hacer.
Didest
0

¿Por qué no, para cada posición i , elegir aleatoriamente de todos los elementos que no sean i ? Por ejemplo, puede elegir un índice en la matriz original de [0..n-2] , y si obtiene j> = i , usa j + 1 .

palmadita
fuente
3
¿Eso hace que todos los trastornos sean igualmente probables?
David Eppstein
oh, buen punto: esto colocaría elementos más adelante en la matriz preferentemente antes en la matriz. Si tuviera que llenar las ranuras en la matriz de destino en un orden aleatorio, todas las alteraciones serían igualmente probables (por simetría).
pat