Existe-t-il un algorithme efficace pour trouver le i-ème Dearrangement?

Voici l'arrière-plan de cette question. Des amis et moi jouions à un jeu où tout le monde devait offrir un cadeau à une autre personne. Afin de déterminer qui doit offrir un cadeau à qui, nous décidons de tirer au sort. Mais le problème est que quelqu'un pourrait finir par se donner des cadeaux, ce qui n'est pas drôle. Vous pouvez voir que le nombre attendu de ces malheureux est de 1, ce qui arrive donc assez fréquemment.

À cet effet, le Dearrangement semble être un bon choix. Si je peux assez générer un désarrangement, alors je peux simplement choisir un désarrangement et l'utiliser pour décider qui offrira à qui.

La génération de désarrangement aléatoire pourrait être effectuée avec la méthode de Las Vegas. Mais le problème est qu'il n'a attendu que le temps d'exécution polynomial. J'en suis donc venu à ce problème de trouver un i-ème arrangement. Si je peux choisir aléatoirement un i dans [1, D_n], et utiliser un algorithme de temps polynomial (efficace) dans le pire des cas pour obtenir le i-ème dearrangement, alors c'est fait.

En fait, c'est peut-être une bonne question, mais elle est mal formulée dans sa forme actuelle. Les algorithmes bien connus pour générer des dérangements aléatoires ont un temps attendu linéaire, mais c'est peut-être un problème ouvert de trouver un algorithme de temps polynomial dans le pire des cas.

Voir par exemple: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (et diapositives: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )

Pourquoi pas, pour chaque position i , choisir aléatoirement parmi tous les éléments autres que i ? Par exemple, vous pouvez choisir un index dans le tableau d'origine parmi [0..n-2] , et si vous obtenez j> = i, vous utilisez j + 1 .