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.