Losowanie bez powtórzeń

Koziołek

1 Teoria
2 Możliwe Rozwiązania
     2.1 losowanie ze sprawdzaniem
     2.2 losowanie z usuwaniem
3 Praktyka

Teoria

Jednym z najczęściej spotykanych problemów jest wylosowanie ze zbioru Z pewnej liczby elementów N tak by wylosowane elementy nie powtórzyły się. Najprostszymi przykładami takiego losowania jest lotek czy wybór "ochotnika" do odpowiedzi w klasie. Problematyczną sprawą jest to jak należy zrobić by liczby naprawdę się nie powtarzały.

Możliwe Rozwiązania

losowanie ze sprawdzaniem

Algorytm losowania ze sprawdzaniem polega na sprawdzeniu czy wylosowana liczba nie została już wylosowana i jeżeli nie to jest zwracana, a jeżeli tak to losowanie jest powtarzane. Jest to typowy przykład metody "brute force", która ma pewną wadę. Jeżeli ze zbioru chcemy wylosować dużo liczb to szansa na powtórzenie wylosowanej liczby rośnie, a co za tym idzie konieczność powtórnego losowania też rośnie. Jeżeli generator losowy jest wadliwy i preferuje pewne wyniki (co jest normalne w maszynach liczących) to szansa na powtórzenie znowu rośnie. Algorytm jest rekurencyjny i co za tym idzie może doprowadzić do przepełnienia stosu lub przekroczenia ilości rekurencji. Do zalet tego algorytmu należą prostota i mała złożoność implementacji.
Najprostszą realizacją tego algorytmu jest stworzenie tablicy bitów (boolean'ów), w której każda komórka odpowiada kolejnej liczbie. Losujemy liczbę i sprawdzamy czy komórka i-ta ma wartość prawda jak tak to liczba jest unikalna i ją zwracamy jak nie to powtarzamy losowanie.

losowanie z usuwaniem

Algorytm ten jest bardziej skomplikowany niż poprzedni, ale nie jest wrażliwy na powtórzenia, bo takowe w nim nie występują. Opiera się o listę wiązaną, a w ogólności zbiór uporządkowany z dostępem po indeksie, z którego wylosowana wartość jest automatycznie usuwana. Działa to w następujący sposób. Po wylosowaniu elementu jest on usuwany ze zbioru i zwracany do wywołującego. Kolejne losowanie odbywa się z mniejszego zbioru. Do wad należy czasochłonność ze względu na czas dostępu do poszczególnych elementów zbioru jednak odpowiednia implementacja wyszukiwania pozwala na skrócenie tego czasu. Zaletą jest usunięcie problemu powtórzonego wyniku losowania.

Praktyka

Przykładowa implementacja obu algorytmów w języku Java.

import java.util.LinkedList;
import java.util.List;
 
public class LosowanieBezPowtorzenMain {
 
    public static final int SIZE = 6;
 
    public static void main(String[] args) {
        LosowanieBezPowtorzenZUsuwaniem bezPowtorzenZUsuwaniem = new LosowanieBezPowtorzenZUsuwaniem(
                SIZE);
        LosowanieBezPowtorzenZeSprawdzaniem bezPowtorzenZeSprawdzaniem = new LosowanieBezPowtorzenZeSprawdzaniem(
                SIZE);
 
        for (int i = 0; i < SIZE; i++) {
            System.out.println(bezPowtorzenZUsuwaniem.get() + " : "
                    + bezPowtorzenZeSprawdzaniem.get());
        }
    }
}
 
class LosowanieBezPowtorzenZeSprawdzaniem {
 
    // tablica bitów przechowująca liczby
    private boolean[] liczby;
 
    // aktulna wielkość tablicy
    private int size;
 
    // konstruktor przyjmuje jako argument wielkość zbioru
    public LosowanieBezPowtorzenZeSprawdzaniem(int size) {
        // tworzymy tablicę bitów
        liczby = new boolean[size];
        this.size = size;
        // Wypełniamy ją danymi
        for (int i = 0; i < size; i++) {
            liczby[i] = true;
        }
    }
 
    public int get() {
        // losujemy liczbę
        int i = (int) (Math.random() * this.size) + 1;
 
        // sprawdzamy czy taką liczbę już wylosowano jeżeli na pozycji i-tej
        // znajduje się true to znaczy, że liczba nie była wylosowana
        if (liczby[i - 1] == true) {
            // oznaczmy liczbę jako wylosowaną
            liczby[i - 1] = false;
            return i; // zwracamy liczbę
        } else {
            // liczba się powtórzyła. Ponawiamy losowanie
            return get();
        }
    }
}
 
class LosowanieBezPowtorzenZUsuwaniem {
 
    // Lista liczb
    private List<Integer> liczby;
 
    // wielkość początkowa
    private Integer size;
 
    // inicjacja obiektu
    public void init() {
        // tworzymy zbiór liczb
        liczby = new LinkedList<Integer>();
        // dodajemy kolejne liczby do zbioru
        for (int i = 1; i < this.getSize() + 1; i++) {
            liczby.add(new Integer(i));
        }
    }
 
    // losowanie
    public Integer get() {
        Integer i = (int) (Math.random() * size);
        i = liczby.get(i);
        liczby.remove(i);
        this.size = liczby.size();
        return i;
    }
 
    // zwraca wielkość zbioru
    private Integer getSize() {
        return size;
    }
 
    // konstruktor jako parametr przyjmujw wielkość zbioru.
    public LosowanieBezPowtorzenZUsuwaniem(Integer size) {
        if (size <= 0)
            throw new IllegalArgumentException("Wielkość musi być większa od 0");
        this.size = size;
        init();
    }
 
}

0 komentarzy