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 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 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:     xZ[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 N
a,b  – liczby określające całkowity przedział losowania, b - an, a,b 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 N
j   wykorzystywane do przeszukiwania tablicy T[ ].  j 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:     xa + 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 =


...



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

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