algorytm.org

Losowanie bez powtórzeń

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Losowanie bez powtórzeń
Ocena użytkowników:***** / 14
SłabyŚwietny 
Wpisany przez Andrzej Borucki, 08 grudnia 2011 15:28

Załóżmy, że mamy wylosować k liczb z n (oczywiście k ≤ n).
Aby uniknąć powtórzeń bierzemy tablicę numbers wielkości n i wypełniamy ją kolejnymi liczbami.
Losujemy indeks r pomiędzy 0 a n-1, liczba spod tego indeksu jest naszą wylosowaną.
Teraz przenosimy ostatnią liczbę w tablicy do pozycji r: numbers[r] = numbers[n - 1] i zmniejszamy n o jeden.

Algorytm ten można przedstawić następującym schematem blokowym:
schemat blokowy losowania bez powtórzeń

Przykład:

Załóżmy, że chcemy wylosować 3 z 5 liczb (k = 3, n = 5).
Tworzymy pięcio-elementową tablicę i wypełniamy ją liczbami numbers = [1, 2, 3, 4, 5]
Losujemy liczbę pomiędzy 0 a 4. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 3 (indeksy w tablicy liczymy od 0). Czyli naszą wylosowaną liczbą jest 3.
Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [1, 2, 5, 4, 5].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [1, 2, 5, 4].
Losujemy liczbę pomiędzy 0 a 3. Wylosowaliśmy indeks 0. Pod tym indeksem znajduje się liczba 1. Czyli naszą wylosowaną liczbą jest 1.
Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [4, 2, 5, 4].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [4, 2, 5].
Losujemy liczbę pomiędzy 0 a 2. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 5. Czyli naszą wylosowaną liczbą jest 5.
Wylosowaliśmy zatem liczby: 3, 1 oraz 5.
Zwróć uwagę, że wylosowane liczby nie powtarzają się mimo tego, że podczas naszego procesu dwa razy wylosowaliśmy indeks 2

Przykład w JavaScript:

k
n

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Andrzej BoruckiC#
.cs
.cs
***** / 7
dawidex44C/C++C++
.cpp
.cpp
***** / 2
Tomasz LubińskiJavaScript
.js
.js
***** / 5
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 września 2012 08:26
Komentarze
photo
-8 # Magda 2011-12-12 14:43
A w Mathematice jak to będzie wyglądać?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz