Strona główna » Algorytmy » Artykuły » Losowanie bez powtórzeń
 

Losowanie bez powtórzeń

https://mattomatti.com/a83

Wstęp

Losowanie bez powtórzeń jest to problem, który każdy programista powinien rozwiązać prędzej czy później. Istnieje wiele różnych sposobów na jego rozwiązanie. Każdy z nich ma zalety jak również wady. Umiejętne dostosowanie algorytmu podczas pisania programu jest bardzo ważnym elementem.

Problem

Losowanie bez powtórzeń polega na wylosowaniu k elementów z n elementowego zbioru tak, aby żadna z wartości w wylosowanej tablicy się nie powtarzała. Z reguły zakłada się, że elementem jest liczba, ale niekoniecznie tak musi być w każdym przypadku. Losować można elementy dowolnego typu: liczby całkowite, naturalne, rzeczywiste albo mogą być znakiem lub fragmentem tekstu. Jednak po nadaniu liczbowych identyfikatorom elementom z dowolnego zbioru zadanie upraszcza się do losowania liczb.

Najprostszy algorytm polega na wczytaniu od użytkownika zbioru elementów, a następnie ile elementów ma zostać wylosowanych. W tym momencie można sprawdzić czy wczytana wartość k nie jest większa od liczby elementów n w zbiorze. Losowanie polega na pobraniu kolejnej wartości ze zbioru, a następnie sprawdzeniu czy takiego elementu nie ma na liście. Jeśli jest to losowana jest kolejna wartość, w przeciwnym razie wylosowany element jest dopisywany na listę wylosowanych elementów. Losowanie powtarza się aż lista wynikowa będzie miała k elementów.

Prosta implementacja

Kod

Przyjmijmy, że program ma symulować loterię liczbową. W pudełku znajduje się n karteczek z liczbami od 1 do n. Losowanie polega na wylosowaniu k karteczek. Wtedy najprostsza implementacja algorytmu wyglądałaby tak:

  1. int* losujLiczby(int k, int n) {
  2.   int* lista_w = new int[k];
  3.   int i = 0;
  4.   while (i < k) {
  5.     int t = rand() % n + 1;
  6.     if (szukajLiczby(lista_w, i, t) == -1) {
  7.       lista_w[i++] = t;
  8.     }
  9.   }
  10.   return lista_w;

(1.) Funkcja zwraca listę wylosowanych liczb na podstawie wprowadzonej wartości k i n. (2.) Zaalokuj pamięć pod listę wynikową i (3.) ustal, które miejsce na liście jest obecnie zapisywane. (4.) Dopóki lista nie jest w pełni zapełniona: (5.) wylosuj liczbę, (6.) sprawdź czy wartość występuje na liście. (7.) Jeśli nie występuje to dopisz na listę i zwiększ indeks i. (9.) Na koniec zwróć tablicę wynikową.

Powyższa funkcja potrzebuje funkcja szukajLiczby(), która sprawdza czy na liście występuje dana liczba. W przypadku jej znalezienia zwracana jest pozycja na liście, a jeśli wartość nie występuje to zwracana jest wartość -1.

  1. int szukajLiczby(int* lista, int n, int a) {
  2.   for (int i = 0; i < n; i++) {
  3.     if (lista[i] == a) {
  4.       return i;
  5.     }
  6.   }
  7.   return -1;
  8. }

Inna implementacja

Uzasadnienie

Warto zwrócić, że poprzednia funkcja działa prawidłowo dla dowolnego k oraz n, ale program ma bardzo poważną wadę: zapętlenie. W pewnym momencie program może zacząć losować już wylosowane wartości. To z kolei spowoduje całkowite "wstrzymanie" programu. Oczywiście program będzie cały czas działał, ale nie zakończy pracy. Są to skrajne przypadki, ale należy wziąć pod uwagę fakt, że może takie zawieszenie nie będzie miało miejsce, ale może opóźnić zwrócenie wyniku.

Drugi pomysł na rozwiązanie podanego problemu różni się sposobem losowania. Przed rozpoczęciem losowania liczb zostaje utworzona lista n liczb. Losowanie polega na wylosowaniu numeru indeksu elementu na zadeklarowanej wcześniej liście. Wylosowany element jest przepisywany na listę wynikową, następnie zamieniany z ostatnim elementem na liście wszystkich liczb. Następnie długość listy n zostaje zmniejszona o 1.

Powyższy rozwiązanie gwarantuje, że program zakończy działanie w liniowej złożoności czasowej . Jego wadą jest wysokie zapotrzebowanie na pamięć komputera.

Implementacja

Poniższy kod rozwiązuje wcześniej postawiony problem loterii, ale wykorzystują nową metodę.

  1. int* losujLiczby(int k, int n) {
  2.   int* lista_liczb = new int[n];
  3.   for (int i = 0; i < n; i++) {
  4.     lista_liczb[i] = i + 1;
  5.   }
  6.   int* lista_w = new int[k];
  7.   for (int i = 0; i < k; i++) {
  8.     int t = rand() % n;
  9.     int pom = lista_liczb[t];
  10.     lista_w[i] = pom;
  11.     lista_liczb[t] = lista_liczb[n - 1];
  12.     lista_liczb[n - 1] = pom;
  13.     n--;
  14.   }
  15.   delete[] lista_liczb;
  16.   return lista_w;
  17. }

(1.) Nagłówek funkcji pozostaje taki sam. (2.) Przygotuj listę wszystkich wartości i (3. - 5.) wypełnij wartościami od 1 do n. (6.) Zaalokuj pamięć pod listę wynikową. (7.) Następnie k razy: (8.) wylosuj indeks kolejnego elementu i (9.) zapamiętaj wartość t-tego elementu. (10.) Dopisz na listę wylosowanych liczb nową wartość i (11. - 12.) zamień t-tą wartość z ostatnią na liście. (14.) Skróć długość listy z której są losowane wartości. Na koniec (15.) usuń niepotrzebną listę i (16.) zwróć listę wylosowanych liczb.

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   srand(time(0));
  3.   int n, k;
  4.   cin >> n >> k;
  5.   int* lista_w = losujLiczby(k, n);
  6.   for (int i = 0; i < k; i++)
  7.     cout << lista_w[i] << " ";
  8.   delete[] lista_w;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz program, który wylosuje k małych liter alfabetu łacińskiego. Pamiętaj, aby sprawdzić czy wprowadzone dane są prawidłowe.

Przykładowo dla k = 5 program może wypisać:

  1. o e n z a