Fisher Yates Shuffle

Viele Computergames (wie etwa das Spiel «Letterjongg», das ich 2018 im Rahmen des Swiss Open Cultural Data Hackathon programmiert habe) benötigen eine Routine, die n Elemente zufällig mischt. Nun gehört ein shuffle-Algorithmus nicht zum Standardrepertoire der Websprache Javascript, sondern lediglich die Methode random() des Math-Objekts. Wie also findet eine Zufallszahl zwischen 0 und 1 den Weg zum zufälligen Mischen von Spielsteinen oder -karten?

Eine elegante Antwort formulierten 1948 die beiden britischen Mathematiker und Statistiker Ronald Fisher und Frank Yates in ihrem Standardwerk Statistical tables for biological, agricultural and medical research (3. Auflage S. 26f., bzw. 6. Auflage S. 37f.). Ihr Verfahren: Wähle zufallsbasiert ein Element eines geordneten Arrays von n Elementen und vertausche es anschliessend mit dem letzten Arrayelement. Wähle anschliessend ein weiteres Zufallselement, diesmal allerdings aus der Menge n-1, und vertausche es mit dem zweitletzten Arrayelement. Wiederhole die Prozedur sinngemäss bis zu den letzten zwei verbleibenden Elementen.

Als Beispiel dient ein Array mit der Buchstabenfolge A B C D. Eine Zufallsauswahl ergibt zum Beispiel B, das mit dem letzten Element D vertauscht wird und A D C B ergibt (vertauschte Elemente unterstrichen). Eine Zufallsauswahl aus den ersten drei Elementen ergibt A, was durch einen Tausch mit dem zweitletzten Element zu C D A B führt. Eine weitere Wahl aus zwei Elementen ergibt C, und der letzte Tausch, diesmal mit dem drittletzten Element, führt zum (nun zufallsbasierten) Endergebnis D C A B.

Gegeben sei also ein geordneter Array arr=[0,1,2...n]. Für das zyklische Verfahren benötigen wir eine n-1-mal drehende Schleife, deren Zähler i wir für einmal rückwärts ablaufen lassen. Innerhalb der Schleife wählen wir mittels der Methode Math.random()*n (bzw. in der Folge *n-1, *n-2 usw.) zufällig eine Zahl aus, runden sie mittels Math.floor() auf die nächste ganze Zahl ab und speichern sie in der Variablen j. Schliesslich vertauschen wir die jeweilige Zufallsauswahl mit dem letzten (zweitletzten, drittletzten etc.) Arrayelement arr[i-1] mittels der Variablen k als Zwischenspeicher. Das Ergebnis

function shuffle(n) {
  for (i=n; i>0; i--) {
    var j=Math.floor(Math.random()*i);

    var k=arr[i-1];
    arr[i-1]=arr[j];
    arr[j]=k;
  }
}

oder, noch einfacher, als Pfeilfunktion mit destructuring assignment,

shuffle=n=> {
  for (i=n; i>0; i--) {
    let j=Math.floor(Math.random()*i);
    [arr[j],arr[i-1]]=[arr[i-1],arr[j]];
  }
};

wird nun jeden geordneten Array arr mit n Elementen zufällig neu anordnen, wie das Beispiel «Letterjongg» zeigt.

 

2200 Sekunden

Ende 2006 erhielt die Programmleitung des damaligen Schweizer Radios DRS 2 (heute Radio SRF 2 Kultur) den Auftrag, die Vermittlung von Wissen zu stärken. Eine Wissenschaftsredaktion wurde aus der Taufe gehoben, und als neues Angebot in der Morgen-Primetime liessen sich meine Programmleitungskollegen Maria Ossowski und Peter Burri ein attraktives populärwissenschaftliches Format einfallen: «100 Sekunden Wissen», eine tägliche Radiorubrik, ausgestrahlt von Montag bis Freitag um 6.55 und um 10.20 Uhr.

Seit dem Anfang ich mit dabei, bis auf den heutigen Tag. 2021 gab's insgesamt 2200 Sekunden Wissen aus meiner Feder: von gebrochenen Preisen, Nadeln und Panzerknackern über das Schweizer-Käse-Modell, den Marshmallow-Test und den Faradayschen Käfig bis hin zur Tinte, dem Flipperkasten und dem Hashtag.

Apropos Sekunde:

 
 
 
 
 
 

2:01

Dieser Beitrag (mp3, ogg) entstand im Auftrag von Radio SRF 2 Kultur und wurde am 10. Juli 2013 in der Rubrik «100 Sekunden Wissen» ausgestrahlt.

Embraceable You

Wenn Musiker ihren Gedanken freien Lauf lassen, entsteht entweder grundlegend Neues – oder aber es kommt längst vergessen Geglaubtes zum Vorschein. So geschehen in der heutigen Bandprobe, als Gitarrist Christoph Thiel den Klassiker «Embraceable You» anstimmte. Sage und schreibe 16 Jahre ist es her, dass wir den Song zum letzten Mal gespielt haben (Peter Widmer voc, Jean-Luc Gassmann p, Christoph Thiel g, Corner Sidler dr, myself b). Aber die Aufnahme von 2005 hat trotz ihres Alters keinen Staub angesetzt.

 
 
 
 
 
 

6:52

Multimedia Awards

Jedes Jahr veranstaltet das Institut für Multimedia Production der Fachhochschule Graubünden und der Hochschule der Künste Bern eine rauschende Gala. Die Bühne des Plaza Klubs Zürich gehörte dieses Jahr den grossartigsten studentischen Medienbeiträgen, die im vergangenen Jahr in meinen Modulen entstanden und auf der Medienplattform «Digezz» publiziert worden sind. Mal federleicht und heiter, mal hintergründig und erdenschwer: Die für die Multimedia Night nominierten Projekte sind Multimedia at its best.

Die Fachjury – Martina Fehr, Direktorin des MAZ in Luzern und Präsidentin der Stiftung «Schweizer Presserat»; Sarah Rosenwald, Senior Concept Developer der Zürcher Livekommunikations-Agentur Standing Ovation; Seline Freiburghaus, Grafikdesignerin und Multimediaproduzentin der Berner Werbeagentur Casalini – war um ihren Job nicht zu beneiden. Sie hat ihre Wahl getroffen: Die Multimedia Awards des Jahres 2021 (Tusch!) gehen an «Raum für alle», eine aufrüttelnde Aufklärungsaktion über sexuelle Belästigung und das Unbehagen junger Frauen auf dem Nachhauseweg, an «Lifere ond Lafere», einer überbordend originellen multimedialen Liebeserklärung an den Appenzeller Dialekt, und an «Nasa Astronaut x Jet Pilot», einer eindrucksvoll inszenierten Begegnung zweier Schweizer Superstars, des Astronauten Claude Nicollier und der Kampfpilotin Fanny Chollet. Der Publikumspreis schliesslich geht an «The Ethereum Hunter», einer virtuos animierten filmischen Parabel über die (selbst-) zerstörerischen Folgen menschlicher Gier.

Es sind Produktionen wie diese, die so viel mehr sind als bloss «professionell»: Es sind eigentliche Fenster in mögliche Zukünfte von Medien und Kommunikation.

Vully Blues Festival

Was für ein Abend: Seite an Seite mit Tiza Brown, Philipp "Bluedög" Gerber und Dominic Shoemaker haben Blues Green am 14. Vully Blues Festival in Praz gespielt: In der Bigband-Besetzung Barbara Andrey (voc), Lucio Crivellotto (voc, g), Christoph Thiel (voc, g), Jean-Luc Gassmann (p), Denis Pittet (tp), André Rossier (as), Markus Karl (ts), Daniel Gaggioli (bar), Willy Marti (dr) und myself (b) haben wir das «Blues boat» gerockt. Blues Green und der Vully Blues Club: Es wird nicht das letzte Mal gewesen sein.


Blues Green, 14. Vully Blues Festival, 5. November 2021. (Bild: Christophe Losberger)

 
 
 
 
 
 

4:39

 
 
1 ... 5 6 7 8 9 ... 47