Der Jojo hat ein kleines Skript geschrieben, das einem die Moderation von Julklapp-Runden (bei denen heißt das wohl "Wichteln", in den USA "Secret Santa") erleichtern soll. Das Problem ist ja immer, dass jemand sich selbst ziehen könnte. Dafür gab es bislang zwei Lösungen:
- Man setzt sich in gemütlicher Runde zusammen, wirft alle Namenszettel in einen Hut und zieht reihum. Sobald sich jetzt jemand selbst zieht, werfen alle ihre Zettel wieder in den Hut und das Ganze startet von vorne
- Man hat einen Moderator, der die Zettel zieht und zusieht, dass keiner sich selbst zieht. Das ist insbesondere – wie Jojo richtig erkannt hat – bei Julklapprunden in der Blogosphäre unerlässlich. Leider kann der Moderator dadurch nicht selbst mitmachen, weil ihm alle Geheimnisse offenbar sind.
Die dritte Lösung ist jetzt, die Ziehung zu automatisieren – das macht Jojos Skript ganz wunderbar. Das Skript hat nur ein Problem: Der Algorithmus für die zufällige Permutation der Teilnehmerliste hat einen unendlichen Aufwand – er terminiert potentiell nicht. Die Liste wird quasi so lange gemischt und überprüft, bis mal eine ordentlich gemischte Liste herauskommt.
Wir (der Arne und ich) haben beim Mittagessen überlegt, ob man den Aufwand für den Mischalgorithmus nicht sogar linear machen könnte. Man muss den jungen Informatikstudenten ja sinnvolle Alternativen bieten und nicht nur billig ihre Lösungen kritisieren 🙂
Meine spontane Idee war, das Zufallselement zu eliminieren und zu sagen, dass jeder auf der Liste seinen jeweiligen Nachfolger beschenkt, der letzte dann den ersten. Das ist aber dann dumm, wenn z.B. zwei in der Liste deshalb nebeneinander stehen, weil sie sich kennen. Außerdem kann jemand, der die Liste kennt, ja dann alle Geheimnisse einsehen.
Nach vielen Diskussionen hat Arne dann folgendes Verfahren entwickelt:
Der Handt-Niemannsche Julklappalgorithmus
- Man geht einmal die Indizes der Teilnehmer von vorne bis hinten durch und tauscht das Element am aktuellen Index mit einem beliebigen zufälligen aus der Liste.
- Das war Arnes Teil – der sorgt dafür, dass der Aufwand linear bleibt, weil man tatsächlich die Liste der Teilnehmer nur einmal durchgehen muss und sie trotzdem gemischt werden.
- Wir können natürlich nicht sichergehen, dass bei dem o.g. Mischen nicht eventuell die Reihenfolge beibehalten wird. Also kommt als nächstes meine Idee doch noch zum Tragen:
- Jeder in der neuen Liste beschenkt seinen Nachbarn zur Rechten, der letzte natürlich den ersten.
Es ist vielleicht noch anzumerken, dass die „Liste“ natürlich ein Array ist, d.h. bei der die einzelnen Elemente wahlfrei mit konstantem Aufwand auslesbar sind, nur dann bleibt der Aufwand linear.
Wirklich schöne Ideen 🙂 Das Terminierungsproblem hab ich natürlcih auch bemerkt. Allerdings erschien mir der Metalevelaufwans für einmal Wichteln im Jahr etwas zu hoch 😀
Die Teilnehmer in der Reihenfolge durchzumischen und jeden seinen Nachbarn bewichteln ist wirklich schicker. Zumal es nichtmal mehr Schreibaufwand als mein jetziges macht 😀
Aber die ultimative Lösung wäre eine rekursive Funktion zum Finden der Permutation *grins* !!!
Liste hab ich das genannt, weil hier ja auch Nichtinformatiker mitlesen.
Pingback: Blogwerk » Nerdklapp
Pingback: Jojos illustrierter Blog » do it the computer science way
Also, also, meine Herren (Frauen?) Informatiker, das geht aber noch besser. Letztlich ist doch der eine Teil des Problems bereits durch den ursprünglichen Vorschlag hier erschlagen: Man muss eine zufällig permutierte Liste der Teilnehmer bekommen, und dann beschenkt eben jeder den nächsten Nachbarn. Damit reduziert sich das Problem auf die Frage, wie man nun vernünftig eine permutierte Liste (Array, Vektor, whatever) bekommt, deren Permutationen bitte alle gleiche Wahrscheinlichkeit haben sollen. Die genannte Lösung „Man geht einmal die Indizes der Teilnehmer von vorne bis hinten durch und tauscht das Element am aktuellen Index mit einem beliebigen zufälligen aus der Liste.“ klappt leider *nicht* so richtig, weil … äh, jetzt hab ich die Begründung vergessen. Jedenfalls erreicht man eine gleichverteilte permutierte Liste genau dadurch, dass man durch die Liste geht und jedes Element mit einem zufälligen *rechts von diesem Element stehenden* Element vertauscht, nicht mit einem zufälligen Element der gesamten Liste. Der Aufwand bleibt jedenfalls der gleiche, und nachher fällt mir hoffentlich auch noch die Begründung für gerade diese Vertauschung ein. Nichts für ungut, cstim
Nachtrag: Die beschriebene zufällige Permutation ist die Standard-Vorgehensweise, auch genannt „Fisher-Yates Shuffle“ http://www.nist.gov/dads/HTML/fisherYatesShuffle.html http://www.stanford.edu/~blp/writings/clc/shuffle.html und http://en.wikipedia.org/wiki/Random_permutation
Aber da Jojo jetzt sowieso die php-Funktion shuffle( ) verwendet, benutzt er eben genau sowas schon.
Boah ey,
Informatiker können sogar das altbewährte Wichteln komplizieren!
Wieso verkomplizieren? Ist halt Nerdwichteln.
Ich stell mir gerade die Frage, ob der Fisher-Yates-Shuffle nicht an sich ausreicht, um eine passende Belegung zu finden. Es kann doch keins der Elemente auf sich selbst geshufflet werden, wenn ich nur nach rechts tausche. Dann brauche ich das mit den Nachfolgern doch gar nicht mehr, oder?
cstim: kannst du mal rausbekommen warum man durch das tauschen mit einem beliebigen Element (also nicht nur rechts in der Liste) keine Gleichverteilung der Permutationen bekommt?
@Jojo: http://www.techuser.net/randpermgen.html erzählt ganz schön, warum man das Tauschen mit der rechten Hälfte macht (übrigens einschließlich des Elements selber). Ich würd’s so zusammenfassen, dass man auf diese Weise die rekursive Vorgehensweise beim Aufschreiben einer Permutation korrekt abbildet: Für die erste Position hab ich die Auswahl zwischen allen N Elementen, für die nächste Position hab ich die Auswahl zwischen den N-1 übrig gebliebenen Elementen (nämlich alle außer denen, die ich im linken Teil bereits gewählt habe) etc.
Der Beweis, dass bei dem Fisher-Yates Shuffle alle Permutationen gleich wahrscheinlich sind, ergibt sich daraus, dass man zu jeder Permutation genau einen Zweig (Kante) des Entscheidungsbaums (Graphen) aufschreibt und man nämlich N! Zweige (Kanten) bekommt, was ja auch exakt die Anzahl der möglichen Permutationen darstellt. Das Auftreten einer bestimmten Permutation hat dann korrekterweise die Wahrscheinlichkeit 1/N!.
Bei dem intuitiven Algorithmus mit einem Tausch mit einem beliebigen Element kann man den Fehler feststellen, wenn man sich ebenfalls den Entscheidungsbaum aufzeichnet: Bei jeder Position k wird eine Entscheidung zum Tausch mit eines der N-1 Elemente getroffen. Da wir N Positionen haben, verzweigt sich der Entscheidungsbaum in (N-1)^N Zweige (Kanten). Bsp N=3: (N-1)^N=8 > N!=6, man hat also in diesem Fall mehr Zweige als richtigerweise nötig wären, was wiederum bedeutet, dass einige der Permutationen öfter vorkommen als andere, welches wiederum bedeutet, dass die Permutationen nun mit unterschiedlicher Wahrscheinlichkeit auftreten. q.e.d.