Gewichteter Zufall


Kleine Vorgeschichte oder die Problemstellung

Vor der Zwischenprüfung zum Fachinformatiker für Anwendungsentwicklung, wollte unser Lehrer mit uns noch mal ein paar Prüfungsaufgaben durchgehen. Damit nicht immer die selben Schüler drankommen nämlich, jene die die Antwort wissen und sich melden bzw. damit nicht vom Lehrer willkürlich Schüler drangenommen werden, hatte unser Lehrer eine Idee. Und zwar sollten wir in der ersten halben Stunde des Unterrichts ein Programm entwicklen, welches es ihm ermöglichte zufällig einen Schüler auszuwählen, aber mit der Einschränkung, dass ein Schüler, der gerade dran gewesen ist, mit einer geringeren Wahrscheinlichkeit noch mal von dem programm ausgewählt wird, als ein Schüler, der noch keine Frage beantworten musste.

Zusammengefasst sollte also folgendes Programm entwickelt werden: Aus einer Liste von Namen solte zufällig ein Name gezogen werden. bei wiederholtem ziehen eines Namens, soll der zuvor ermittelte Name mit einer geringeren Wahrscheinlichkeit gezogen werden, als ein Name, der noch nicht gezogen wurde.

Eine mögliche Lösung des Problems

Nach dem von uns einige Lösungsvorschläge gemacht wurden, die aber irgendwie nicht so ganz befriedigend waren, machte dann unsere Lehrer einen Vorschlag. Im ersten Schritt ermittelt man eine Zufallszahl mit Hilfe des Zufallsgenerators und der entsprechenden Funktion der Programmiersprache. Diese liefert in der Regel einen Wert zwischen 0 und 1. Jetzt folgt der entscheidenede Schritt in dem man die Wurzel aus dieser ermittelten Zufallszahl zieht. Damit erziehlen wir eine quadratische Verteilung. Aus 0,5 wird so zum Beispiel 0,707. Dann muss man nur noch durch ein paar Rechenoperationen dafür sorgen, dass die ermittelte Zufallszahl im gültigen Wertebereich liegt.

////////////////////////////////////////////////////////////////////////////////
// Procedure : WeightedRandom
// Comment   : Generates a weighted radomizes number
function WeightedRandom(AMaxCount: Cardinal): Cardinal;

  function NRoot(ARadicant, N: Double): Double;
  begin
    result := Power(ARadicant, 1 / N);
  end;

var
  n                 : Extended;
begin
  n := Random;
  n := NRoot(n, 3);
  n := n * AMaxCount + 1;
  result := Trunc(n);
end;

Im zweiten Schritt muss man jetzt nur noch dafür sorgen, dass ein gezogener Name vor der nächsten Ziehung an den Anfang der Liste eingefügt wird, da ja durch die Gewichtung bevorzugt Namen vom Ende der Liste gezogen werden. Durch die Höhe der Wurzelpotenz lässt sich beeinflussen in wie weit die ermittelte Zufallszahl durch den Zufallsgenerator nach oben "gedrückt" werden soll. So liefert die 2. Wurzel aus 0,5 0,707 und die 3. Wurzel 0,793.

Programmverlauf nach drei Ziehungen:

Screenshot Programm Gewichteter Zufall

Wie man sieht, wandern die gezogenen Namen an den Anfang der Liste und die neu gezogenen Namen befinden sich überwiegend am Ende der Liste.

Downloads


gewichteterzufall.zip Wednesday, 29-Dec-2010 23:45:34 CET 28K

2010-12-29T23:44:47 +0100, mail+homepage[at]michael-puff.de