Mieszanie pseudolosowe

Zadanie mieszania, tasowania (ang. shuffle) zawartości tablicy sprowadza się do wykonywania w pętli zamiany miejscami dwóch elementów tablicy o wylosowanych indeksach. Pętla musi być wykonana tyle razy, aby tasowanie objęło wszystkie elementy – w praktyce wystarcza ilość wykonań równa 3n, gdzie n  jest ilością elementów.

 

Algorytm mieszania pseudolosowego

Wejście
n     liczba elementów w tablicy, n  obrazek N
Z[ ]  – tablica elementów, indeksy rozpoczynają się od 0
Wyjście:

Tablica Z[ ] z potasowaną zawartością

Zmienne pomocnicze
i  –  licznik obiegów pętli. i  obrazek N
x   przechowuje element tablicy Z[ ] przy zamianie zawartości. Typ ten sam, co elementy tablicy Z[ ].
losowa(x)  – funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x  - 1
Lista kroków:
K01: Dla i  = 1,2,...,3n: wykonuj K02...K07 ; tasowanie wykonujemy w pętli
K02:     i1 ← losowa(n) ; losujemy pierwszy indeks
K03:     i2 ← losowa(n) ; losujemy drugi indeks
K04:     x  ← Z[i1] ; zamieniamy miejscami Z[i1] i Z[i2]
K05:     Z[i1] ← Z[i2]  
K06:     Z[i2] ← x  
K07: Zakończ  

Pseudolosowe tasowanie
(C)2012 mgr Jerzy Wałaszek


...

 

Losowanie bez powtórzeń

Zadanie losowania bez powtórzeń można rozwiązać na kilka różnych sposobów. Jeśli przedział <a,b> jest mały (np. zawiera 80 kolejnych liczb Multi-Lotka), to możemy go odwzorować w tablicy, następnie zawartość tej tablicy potasować poprzednio podanym algorytmem i jako wynik zwrócić pierwsze n  elementów. Tasowanie nie dubluje elementów tablicy, zatem otrzymamy n  liczb bez powtórzeń. Taki algorytm posiada klasę złożoności obliczeniowej O(n).

Jeśli przedział <a,b> jest bardzo duży, a n  stosunkowo małe, to postępujemy w sposób następujący. Przygotowujemy pustą tablicę o n  elementach. Losujemy liczbę pseudolosową. Jeśli wylosowana liczba jest już w tablicy, to losujemy ponownie dotąd, aż wylosowanej liczby nie będzie w tablicy. Liczbę dopisujemy do tablicy. Jeśli tablica jest zapełniona, kończymy. W przeciwnym razie powtarzamy losowanie. Algorytm w takiej postaci posiada optymistyczną klasę złożoności obliczeniowej O(n2).

 

Algorytm losowania bez powtórzeń

Wejście
n     liczba określająca, ile liczb pseudolosowych bez powtórzeń należy wylosować, n  obrazek N
a,b  – liczby określające całkowity przedział losowania, b  - a  ≥ n, a,b  obrazek C
Wyjście:

n  różnych od siebie liczb pseudolosowych z przedziału <a,b>

Zmienne pomocnicze
T[ ]  –  tablica przechowująca wylosowane liczby pseudolosowe. Indeksy od 0 do n-1.
i  –  licznik wylosowanych liczb pseudolosowych. i  obrazek N
j   wykorzystywane do przeszukiwania tablicy T[ ].  j  obrazek N
x  – wylosowana liczba pseudolosowa
losowa(x)  – funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x  - 1
Lista kroków:
K01: Dla i  = 0,1,...,n-1 wykonuj K02...K06  
K02:     x  ← a  + losowa(b  - a  + 1) ; losujemy liczbę pseudolosową
K03:     Dla j  = 0,1,...,i  - 1 wykonuj K04 ; sprawdzamy, czy wylosowana liczba jest w T[ ]
K04:         Jeśli T[j] = x, to idź do K02 ; jeśli tak, powtarzamy losowanie
K05:     T[i] ← x ; jeśli nie, zapamiętujemy w T[ ] wylosowaną liczbę
K06:     Wyprowadź x ; wyprowadzamy liczbę na wyjście
K07: Zakończ  

Losowanie bez powtórzeń
(C)2012 mgr Jerzy Wałaszek

a = , b = , n =


...


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe