Secret Santa - Générer des permutations "valides

Question

Mes amis m'ont invitée à la maison pour jouer au jeu du Père Noël secret, où nous sommes censés dessiner un lot et jouer le rôle du "Père Noël" pour un ami du groupe.

Nous écrivons donc tous nos noms et choisissons un nom au hasard. Si l'un d'entre nous se retrouve avec son propre nom, nous procédons à un remaniement et choisissons à nouveau des noms (le raisonnement étant que l'on ne peut pas être son propre Père Noël).

Comme nous sommes sept à jouer, j'ai considéré la "répartition du Père Noël" finale comme une permutation de (1:7) sur elle-même, avec quelques restrictions.

J'aimerais solliciter diverses idées sur la manière dont nous pourrions utiliser Mathematica en particulier ou tout autre langage de programmation ou même un algorithme :

• Liste/impression de TOUTES les allocations "valides" du Père Noël
• Est modulable en fonction du nombre d'amis qui jouent à "Secret Santa".

Answer 1

Ce que vous recherchez est appelé dérèglement (un autre joli mot latin à connaître, comme exsanguination et défenestration).

La fraction de toutes les permutations qui sont des dérangements est proche de 1/e = environ 36,8 % -- donc si vous générez des permutations aléatoires, continuez à les générer, et il y a une très forte probabilité que vous en trouviez une dans les 5 ou 10 sélections d'une permutation aléatoire. (10,1 % de chances de ne pas en trouver dans 5 permutations aléatoires, chaque 5 permutations supplémentaires réduisant les chances de ne pas trouver de dérèglement d'un autre facteur de 10).

Cette présentation est assez terre-à-terre et donne un algorithme récursif pour générer des dérogations directement, plutôt que de devoir rejeter les permutations qui ne sont pas des dérogations.

Answer 2

Je propose ceci :

f[s_List] := Pick[#, Inner[SameQ, #, s, Nor]] & @ Permutations@s

f @ Range @ 4

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2},
 {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

C'est nettement plus rapide que la fonction de Heike.

f @ Range @ 9; //Timing
secretSanta[9]; //Timing

{0.483, Null}    {1.482, Null}

Si l'on ne tient pas compte de la transparence du code, il est possible d'accélérer encore le processus de plusieurs fois :

f2[n_Integer] := With[{s = Range@n},
    # ~Extract~ 
       SparseArray[Times@@BitXor[s, #] & /@ #]["NonzeroPositions"] & @ Permutations@s
  ]

f2[9]; //Timing

{0.162, Null}

Answer 3

Une permutation qui ne fait correspondre aucun élément à lui-même est une dérèglement . Au fur et à mesure que n augmente, la fraction des dérèglements se rapproche de la constante 1/e. Il faut donc (en moyenne) e essais pour obtenir un dérèglement, si l'on choisit une permutation au hasard.

L'article de wikipedia contient des expressions permettant de calculer des valeurs explicites pour de petits n.

Answer 4

Dans Mathematica, vous pourriez faire quelque chose comme

secretSanta[n_] := 
  DeleteCases[Permutations[Range[n]], a_ /; Count[a - Range[n], 0] > 0]

donde n est le nombre de personnes dans la piscine. Ainsi, par exemple secretSanta[4] retours

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2}, 
  {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

Editer

Il semble que le Combinatorica dans Mathematica possède en fait un paquetage Derangements Vous pouvez donc également faire quelque chose comme

Needs["Combinatorica`"]
Derangements[Range[n]]

bien que sur mon système Derangements[Range[n]] est environ 2 fois plus lente que la fonction ci-dessus.

Answer 5

Cela ne répond pas à votre question sur le comptage des dérangements valides, mais donne un algorithme pour en générer un (ce qui pourrait être ce que vous voulez) avec les propriétés suivantes :

1. il garantit qu'il n'y a qu'un seul cycle dans la relation du Père Noël (si vous jouez à 4, vous ne vous retrouvez pas avec 2 couples de Père Noël --> 2 cycles),
2. il fonctionne efficacement même avec un très grand nombre de joueurs,
3. si elle est appliquée équitablement, personne ne sait qui est le Père Noël,
4. il n'y a pas besoin d'ordinateur, seulement de papier.

Voici l'algorithme :

• Chaque joueur écrit son nom sur une enveloppe et place son nom dans un papier plié dans l'enveloppe.
• Un joueur de confiance (pour la propriété n° 3 ci-dessus) prend toutes les enveloppes et les mélange en regardant le verso (où aucun nom n'est écrit).
• Une fois que les enveloppes sont suffisamment bien mélangées, il faut toujours regarder un peu plus loin.
• A