Losowanie bez powtórzeń jest chyba jednym z najczęstszych zadań dla początkujących, zarówno uczących się samodzielnie, jak i na studiach. Często przejawia się w zadaniu typu “utwórz program losujący liczby w Lotto”. Równie często spotykam kod z wydajnością O(evil), którego powstydziłbym się nawet w najbezczelniejszym Lawful Evil – mieszanina randów, srandów, sprawdzania w pętli O(n³) czy wartość jest już znaleziona, alokacji pamięci za pomocą new[] itd.

Jest to w dużej mierze pokłosie sposobu nauczania C++. W tym poście przedstawię proste, czytelne i wydajne sposoby uzyskania tego samego efektu.

Małe zbiory/losujemy większość zbioru

W tym przypadku procedura jest trywialna. Aby uzyskać n elementów zbioru bez powtórzeń:

1. Wymieszaj kontener zawierający możliwe wartości.
2. Weź n pierwszych elementów kontenera.

Procedura ta sensowna przede wszystkim, gdy losujemy znaczącą część zbioru (np. 800 milionów z miliarda elementów zbioru). Za to w przypadku małych zbiorów¹ wejściowych ewentualna różnica w wydajności względem metody przedstawionej niżej będzie niezauważalna.

W kodzie:

shuffle(lotto.begin(), lotto.end(), random);
copy_n(lotto.begin(), 6, ostream_iterator<int>(cout, ", "));

Pełny przykład (używa przedziału <1, 49>, ale zbiór wejściowy może mieć dowolne wartości):

int main()
{
    vector<int> lotto(49);
    iota(lotto.begin(), lotto.end(), 1);
    mt19937 random{random_device{}()};
 
    shuffle(lotto.begin(), lotto.end(), random);
    copy_n(lotto.begin(), 6, ostream_iterator<int>(cout, ", "));
}

[link]
Przykładowy output:

44, 26, 25, 15, 6, 32,

Duży zbiór liczb do losowania

W przypadku, gdy wejściowy zbiór liczb do losowania jest duży¹, procedura losowania n elementów wygląda następująco:

1. Wylosuj wartość i dodaj ją do zbioru unikalnych wartości już wylosowanych.
2. Jeśli zbiór już wylosowanych elementów ma mniej niż n elementów – idź do punktu 1.

W kodzie (używa przedziału <0, 10⁹>, zamiast dis(random) można podstawić funkcję zwracającą wartości z dowolnego zbioru):

unordered_set<int> selected;
uniform_int_distribution dis(0, 1000000000);
while(selected.size() < 100)
    selected.insert(dis(random));

Pełny przykład:

int main()
{
    mt19937 random{random_device{}()};
 
    unordered_set<int> selected;
    uniform_int_distribution dis(0, 1000000000);
    while(selected.size() < 100)
        selected.insert(dis(random));
 
    copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, "\n"));
}

[link]

¹_{Co jest zbiorem małym, a co dużym należy zbenchmarkować samodzielnie i może być zależne od maszyny wykonującej kod, ale estymuję, że do kilku megabajtów można na współczesnych komputerach uznać za mały zbiór.}