Strona główna » Algorytmy » Artykuły » Równomierne Losowanie
 

Równomierne Losowanie

https://mattomatti.com/a0027

Zadanie

Zadanie polega na wylosowaniu z zakresu [min, max] listy złożonej z ile liczb całkowitych. Elementy powinny być losowane z równym prawdopodobieństwem co oznacza, że jeśli losowana będzie lista o długości max - min + 1 to każdy element z przedziału wystąpi na niej dokładnie raz, a kolejność elementów będzie losowa.

Analiza zadania

Przyjmijmy, że n to ilość liczb całkowitych w przedziale. Chcąc rozwiązać zadanie należy zauważyć, że jeśli ile jest wielokrotnością n to każdy element z przedziału [min, max] wystąpi dokładnie k = ile / n. Jednak w przypadku, gdy ile nie jest wielokrotnością n to ponownie każdy element wystąpi dokładnie k razy, ale niektóre z elementów będą miały dodatkowe wystąpienie.

Jeden z najprostszych sposobów jest zastosowanie algorytmu losującego dowolną liczbę, a następnie wstawienie tej liczby na listę pod warunkiem, że spełnia warunki tj. czy występuje już maksymalną ilość razy. Wiąże się to jednak z stały kontrolowaniem ile już występuje elementów każdego typu. Co więcej tego typu algorytm wciaż może losować liczbę, która już nie spełnia warunków i program ponownie będzie przechodził do kolejnego losowania nie wykorzystując w żaden sposób dokonanych obliczeń.

Implementacja

Zdecydowanie lepszym rozwiązaniem jest zastosowanie funkcji tasującej listę oraz wygenerowanie odpowiedniej listy do potasowania. W ten sposób gwarantowana jest skończoność wykonywania z minimalnym potrzebnym czasem obliczeń. Funkcja tasująca przedstawia się następująco:

  1. void tasujListe(int* lista, int n) {
  2.   for (int i = 0; i + 1 < n; i++) {
  3.     int pos = (rand() / (double)RAND_MAX)*(n - i - 1);
  4.     swap(lista[n - i - 1], lista[pos]);
  5.   }
  6. }

Przyjmuje ona dwa argumenty: tablicę liczb lista oraz n - długość tablicy lista. (2.) Dla każdego kolejnego elementu od końca skończywszy na drugim (3.) losowana jest pozycja i (4.) wyróżniony element jest zamieniany z elementem na wylosowanej pozycji.

Posiadając funkcję tasujListe() można napisać funkcję losującą losujRownomiernie(), która będzie losować ile liczb z przedziału [min, max].

  1. int* losujRownomiernie(int min, int max, int ile) {
  2.   int n = max - min + 1;
  3.   int* dane = new int[ile];
  4.   int przepisz = ile/n;
  5.   for (int i = 0; i < przepisz; i++)
  6.     for (int j = 0; j <= n; j++)
  7.       dane[i*n + j] = min + j;
  8.   int* los = new int[n];
  9.   for (int i = 0; i <= n; i++)
  10.     los[i] = min + i;
  11.   tasujListe(los, n);
  12.   for (int i = 0; i <= (ile - przepisz*n); i++)
  13.     dane[przepisz*n + i] = los[i];
  14.   tasujListe(dane, ile);
  15.   return dane;
  16. }

Na początek (2.) określana jest ilość liczb całkowitych w przedziale [min, max] oraz (3.) tworzona jest lista wynikowa dane o długości wskazanej przez argument ile. Następnie (4.) zostaje określona gwarantowana ilość wystąpień każdego z elementów z przedziału. (5. - 7.) Kolejne liczby są przepisywane tyle razy ile wyliczona wartość.

Teraz na liście znajduje się p = ile - przepisz·dane wolnych pozycji. Na tych pozycjach należy umieścić unikalny element z przedziału. W tym celu: (8.) tworzona jest nowa lista i (9. - 10.) zostaje wypełniona kolejnym liczbami całkowitymi z przedziału. Kolejny etap (11.) polega na potasowaniu tej listy. W ten sposób dowolny ciąg p liczb z tej listy zawiera maksymalnie po jednym wystąpieniu każdej liczby z przedziału. Przykładowo (12. - 13.) można przepisać p pierwszych liczb z listy los. Na koniec należy pamiętać o (14.) potasowaniu całej listy włącznie z elementami ustalonymi na początku.

Testowanie funkcji

Poniższa funkcja main() losuje listę o długości ile = 6 liczbami z przedziału [1, 5]. Oznacza to, że każda liczba całkowita z przedziału będzie na wylosowanej liście oraz dokładnie jedna z liczb wystąpi podwójnie.

  1. int main () {
  2.   srand(time(NULL));
  3.   int ile = 6;
  4.   int* dane = losujRownomiernie(1, 5, ile);
  5.   for (int i = 0; i < ile; i++)
  6.     cout << dane[i] << " ";
  7.   cout << endl;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz algorytm do równomiernego losowania listy tak, aby do funkcji losujRownomiernie() przekazywane były tablica liczb typu int oraz jej długość n.