Generator liczb losowych: losowanie z koszyka

Zwykła funkcja losująca (random()) zwraca liczby, które są (w teorii) niezależne od tego, co wylosowało się wcześniej. Oznacza to, że czasem możemy otrzymać długie serie tych samych liczb, co często jest niepożądane. Stosuje się różne techniki, aby temu zapobiegać.

Jedną z najprostszych jest losowanie „z koszyka” - losujemy liczbę z pewnego zestawu, wyciągamy ją z tego zestawu i odkładamy na bok. Gdy zestaw zrobi się pusty, wkładamy z powrotem wszystkie liczby do zestawu i powtarzamy całą procedurę od nowa. Przypomina to trochę wyciąganie kul / kartek z numerami z koszyka / urny itp.

W praktyce nie musimy oczywiście implementować tego dokładnie w taki sposób. Przestawiona niżej funkcja losuje liczbę z tablicy z zadanymi wartościami, zmniejszając za każdym razem zakres losowania i wyrzucając wylosowaną liczbę poza ten zakres.

//Jakiś zestaw liczb, może być wpisany na sztywno
//albo generowany w programie.
int zestawLiczb[iloscLiczb];

//Zakres bieżącego losowania.
//Początkowo losujemy z całego zestawu.
int zakresLosowania=iloscLiczb;

int losujLiczbe(void)
{
  int i, x;

  //losujemy liczbę z zakresu losowania, zmniejszając zakres
  i=random(zakresLosowania);
  zakresLosowania--;
  x=zestawLiczb[i];

  //wyrzucamy wylosowaną liczbę poza nowy zakres losowania
  //zamieniając ją z (pierwszą) liczbą spoza tamtego zakresu
  zestawLiczb[i]=zestawLiczb[zakresLosowania];
  zestawLiczb[zakresLosowania]=x;
  if(zakresLosowania==0) zakresLosowania=iloscLiczb;

  //zwacamy wylosowaną liczbę
  return x;
}

Tego typu losowanie przydaje się na przykład w grach. Szczerze mówiąc na algorytm ten natrafiłem, gdy szukałem informacji na temat Tetrisa, który w taki właśnie sposób generuje nowe klocki.

W serii TGM zastosowano metodę generowania „przyjaznych” sekwencji klocków polegającą na tym, że przechowuje się w historii 4 ostatnio wylosowane klocki. Program następnie losuje klocek tak długo, aż trafi na jakiś spoza historii (losuje z trzech pozostałych).