Algorytm losowego wybierania utworów

Spotkałem się ostatnio z ciekawym problemem, chodziło mianowicie o losowanie piosenek z listy odtwarzania w software’owych odtwarzaczach muzycznych w taki sposób, żeby zapewnić odpowiednią różnorodność utworów oraz niepowtarzalność trafień. Przykładową implementację mojego algorytmu do rozwiązania tej kwestii przeprowadziłem w języku perl.

Ze względu na to, że opracowany algorytm nie miał być uniwersalny, a przeznaczony dla konkretnych zadań można było przyjąć warunki brzegowe upraszczające nieco samą jego konstrukcję oraz implementację. Założyć można było bowiem, że:

1. zakres liczb ograniczony jest w logicznej konsekwencji do naturalnych z wyłączeniem 0,
2. znany jest zakres losowanych liczb, czyli zbiór, na którym będziemy operować,
3. zbiór jest skończony a wartości brzegowe należą do zbioru.

Po ustaleniu warunków dla pracy algorytmu można było przystąpić do najważniejszego zagadnienia – zapewnienia zadowalającej losowości wyników. Funkcje losowe implementowane w językach programowania generują liczby pseudolosowe, których zmienność może pozostawiać wiele do życzenia.

Implementację należało rozpocząć od wylosowania liczby z zakresu nie wykraczającego poza górną granicę zdefiniowanego przez użytkownika przedziału:

#generate single rand in range
my $singleRand = rand($rend);

Następnie przeprowadzono szereg operacji na wylosowanej liczbie mających na celu zmniejszenie prawdopodobieństwa, że dwie kolejno losowane liczby znajdą się w bliskim sąsiedztwie. Na początku do wylosowanej liczby dodano bias (ponieważ rand(); w języku perl losuje liczby typu float, wszystkie pozostałe operacje wykonywane są również na typach zmiennoprzecinkowych, a zaokrąglenie następuje dopiero na końcu działania algorytmu). Wartość bias określona została poprzez odwrotność proporcji ilości poprawnie wylosowanych elementów do oczekiwanej wielkości   zbioru:

#make a bias for random number
my $arrSize = @varArray;
my $arrayFractionBias = $arrSize/$elements gt 0 ? $arrSize/$elements : 1/$elements;
$arrayFractionBias = pow($arrayFractionBias, -1);
$singleRand += $arrayFractionBias;

Jednym zdaniem: im mniej wylosowanych elementów, tym wyższa wartość współczynnika bias dodawanego do wylosowanej liczby. Następnie, w naturalnej konsekwencji dodania bias, należało zadbać o sprawdzenie czy utworzona liczba nadal mieści się w zakresie podanym przez użytkownika:

#keep random number in range
do {
        if($singleRand gt $rend) {
         my $minus = rand($rend);
         if($rstart le 0) {
          $minus = 1;
         } 
          do {
                $singleRand -= $minus;
           } while($singleRand gt $rend);
        } elsif ($singleRand lt $rstart) {
           do {
            $singleRand +=  rand($rend);
           } while($singleRand lt $rstart);
        }
} while($singleRand gt $rend && $singleRand lt $rstart);

W razie potrzeby liczba była zmniejszana albo zwiększana o losową wartość dopóty, dopóki  nie znalazła się w granicach zakresu. Na koniec zabrać należało o zaokrąglenie wyniku oraz sprawdzenie, czy mieści się on w zakresie i nie został wylosowany.

Na potrzeby algorytmu zaimplementowano zaokrąglenie odwrotne do zasad matematycznych :

#round float into int math inversely
my $fraction = $singleRand;
$fraction =~ s/^\d+\.//; 
$fraction = "0.$fraction";

if($fraction ge 0.5) {
        $singleRand = floor($singleRand);
} else {
        $singleRand = ceil($singleRand);
}

Po zaokrągleniu liczby sprawdzono, czy nie jest ona równa 0 lub czy nie znajduje się w uprzednio zdefiniowanej tablicy liczb wylosowanych.

W ogólności algorytm można przedstawić więc następująco:

1. ustal początek, koniec i wielkość zakresu,
2. weź losową liczbę,
3. powiększ ją o odwrotność proporcji ilości poprawnie wylosowanych elementów do oczekiwanej wielkości   zbioru,
4. sprawdź czy liczba po powiększeniu mieści się w podanym zakresie,
   1. jeżeli liczba jest mniejsza niż minimum podanego zakresu powiększaj ją o losową wartość do czasu przekroczenia dolnej wartości zakresu,
   2. jeżeli liczba jest większa niż maksimum podanego zakresu pomniejszaj ją o losową wartość do czasu przekroczenia górnej wartości zakresu,
5. jeżeli liczba jest ujemna zmień jej znak na przeciwny,
6. zaokrąglij liczbę do liczby całkowitej,
7. sprawdź, czy liczba nie jest równa 0 lub nie została już wylosowana,
   1. jeżeli liczba nie została wylosowana podaj jej wartość i wpisz do tablicy wylosowanych liczb,
   2. jeżeli liczba została wylosowana skocz do punktu 1.

Wyniki działania algorytmu prezentują się następująco:

Implementację w języku perl (z opcją rysowania wykresu) można pobrać z linku poniżej notki (tradycyjnie już – ze względów bezpieczeństwa plik jest w formacie *txt).