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

}