skip to Main Content

Losowanie liczb bez powtórzeń. Dwa podejścia, dwa języki (C/C++)

Podzieliłem posta na dwie części, dla języka C oraz C++
Dwa pojęcia pomocnicze, aby było wiadomo co przez te słowa rozumiem:

  • zakres losowanych liczb – To jest przedział liczb naturalnych (od 0 do nieskończoności), z których będziemy wybierali liczby
  • ilość losowanych liczb – Liczba elementów będących w tablicy które się nie powtarzają wewnątrz tablicy

Język C

Pierwsze podejście jest intuicyjne sprawdzające się do takiego algorytmu:

  1. Wylosuj liczbę ‚n’
  2. Sprawdź czy istnieje liczba ‚n’ w tablicy ‚tab’
  3. Jeśli TAK to przejdź do kroku 1
  4. Jeśli NIE to dodaj n do tablicy ‚tab’
  5. Jeśli potrzeba więcej liczb przejdź do kroku 1
Jednak przy losowaniu z małego zakresu liczb o dużej ilości (np. zakres 1..15, ilość liczb 10) może spowodować częsty przypadek gdy wylosowana zmienna n znajduje się już w tablicy. Gdybyśmy chcieli wyliczyć złożoność obliczeniową powyższego algorytmu, to wynik były O(0). Oznacza algorytm który mógł się wcale nie wykonać (np. gdyby zawsze byłaby losowana wartość już istniejąca w tablicy.


Aby znaleźć bardziej czasowo efektywny algorytm. Warto zastanowić się na takim przypadkiem:
Mamy zakres 15 liczb od 1 do 15 i chcemy mieć w tablicy 15 liczb bez powtarzania.

Wynikiem takiego losowania, taki sam jak przetasowanie[1] tablicy z kolejno wartościami od  1 do 15.

[1] – Zna ktoś lepsze tłumaczenie słowa shuffle ?

Algorytm który będzie losował n liczb losowych bez powtórzeń, z zakresu od p do k:

  1. Utwórz tabelę na k-p+1 elementów (tak duży rozmiar aby pomieścić cały zakres)
  2. Przetasować całą tablicę
  3. Wynik znajduje się w pierwszych n elementach

Algorytm na przetasowanie z którego będę korzystał nosi nazwę Fisher–Yates shuffle (algorytm nazwany po jego twórcach Ronald Fisher oraz Frank Yates)

Dla tablicy o nazwie tab i rozmiarze n, kolejne kroki to:

  1. Pętla for od i=n-1 do i>0 krok co i–
  2. Do zmiennej j przypisz losową wartość  w zakresie od 0 do i włącznie
  3. Zamień tab[j] z tab[i]
Moja implementacja wygląda tak:
Parametrami tej funkcji jest:

  • int _array[] – tablica do przetasowania
  • int size – rozmiar tablicy
  • int (*rnd_gen)(int begin,int end) wskaźnik do funkcji która zwraca losową wartość w określonym przedziale od begin do end włącznie. Ten zabieg ma na celu uniezależnienie się od funkcji rand(), w przypadku gdybyśmy chcieli skorzystać z innych generatorów liczb losowych.

Język C++

Przy języku C++ od razu przeskoczę do algorytmu przetasowywania.Otóż tego algorytmu nie trzeba na własną rękę implementować. Funkcję std::random_shuffle można znaleźć w bibliotece algorithm. Pozwala na przetasowanie wewnątrz kontenerów takich jak vector, list itp.

O języku C++ nie ma co pisać, bo wszystko ma w sobie 🙂

Paweł Sołtysiak

Programista, domowy kucharz i "amator amerykańskiej polityki".
Zbieram informacje z całej sieci, po odrzuceniu chwastów i dodaniu swojej opinii publikuje na blogu.

Back To Top