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:
- zakres liczb ograniczony jest w logicznej konsekwencji do naturalnych z wyłączeniem 0,
- znany jest zakres losowanych liczb, czyli zbiór, na którym będziemy operować,
- 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:
- ustal początek, koniec i wielkość zakresu,
- weź losową liczbę,
- powiększ ją o odwrotność proporcji ilości poprawnie wylosowanych elementów do oczekiwanej wielkości zbioru,
- sprawdź czy liczba po powiększeniu mieści się w podanym zakresie,
- jeżeli liczba jest mniejsza niż minimum podanego zakresu powiększaj ją o losową wartość do czasu przekroczenia dolnej wartości zakresu,
- jeżeli liczba jest większa niż maksimum podanego zakresu pomniejszaj ją o losową wartość do czasu przekroczenia górnej wartości zakresu,
- jeżeli liczba jest ujemna zmień jej znak na przeciwny,
- zaokrąglij liczbę do liczby całkowitej,
- sprawdź, czy liczba nie jest równa 0 lub nie została już wylosowana,
- jeżeli liczba nie została wylosowana podaj jej wartość i wpisz do tablicy wylosowanych liczb,
- 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).