Algorytmy

Losowanie bez powtórzeń

  • 2007-12-21 01:35
  • 0 komentarzy
  • 7751 odsłon
  • Oceń ten tekst jako pierwszy
Spis treści

     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();
        }
 
}