e-mail    Debatní kniha    Mapa stránek    Hlavní  
 INT21h 
 

Náhodné pořadí

Zadání 1

Představte si, že máte skupinu závodníků, kteří mají postupně, tedy po jednom, vyrazit na start. Chceme, aby vyráželi v náhodném pořadí. Bez počítače bychom neměli problém - „Hej ty, jseš na řadě!...Kdo další? Třeba ty, poběž!,...“. Ale jak to udělat počítačově?. Ono není problém vybrat ze skupinu závodníků jednoho a pustit ho na start. Problém nastává při pouštění dalších. Musíme si totiž nějak poznamenávat, kteří závodníci už odběhli a musíme náhodně tahat jen z postupně se tenčící skupinky těch, kteří ještě nevyrazili.

Zadání 2

Máme černou obrazovku. Chceme, aby se ní náhodně objevovaly červené tečky, a to tak dlouho, dokud nebude celá obrazovka jednolitě červená. Zde také narážíme na problém, že musíme nějak zařídit, aby se náhodně zaplňovaly jen zatím černé body. Kdybychom pouze tupě generovali náhodná čísla, tak bez skenování obrazovky pixel po pixelu bychom ani nemohli určit, kdy tečkování ukončit. Rovněž by se extrémně protahoval čas k dokončení úkolu. Jak tedy na to?

Postup

Abychom dosáhli univerzálního řešení problému postupného výběru, které by vyhovovalo oběma zadáním, tak si vytvoříme objekt RndEmitor, který nám bude generovat unikátní, tedy ještě nepoužité náhodné hodnoty. Postupně si ukážeme několik variant řešení. Ve všech případech ale použijeme tuto jednotnou kostru programu.
Napřed RndEmitor inicializujeme, potom nám bude v cyklu produkovat náhodné hodnoty a potom ho ukončíme pomocí metody Done.
Program Poradi;
uses Crt; {Pro proceduru Randomize a funkci Random}
const POCET=10;

type RndEmitor = object
  Procedure Init(n:longint);
  Function DejHodnotu:longint;
  Procedure Done;
  end;

Procedure RndEmitor.Init(n:longint);
begin {dummy} end;

Function RndEmitor.DejHodnotu:longint;
begin {dummy} end;

Procedure RndEmitor.Done;
begin {dummy} end;

var a,i:longint;
    rnd:RndEmitor;

begin
Rnd.Init(POCET);
for i:=0 to POCET-1 do
    begin
    a:=Rnd.DejHodnotu;
    writeln(a);
    end;
Rnd.Done;
end.
V textu si postupně ukážeme čtyři možné varianty řešení, které jsem vymyslel. Všechny využívají jako pomocnou strukturu jedmorozměrné pole. Pravděpodobně by se dal problém řešit i pomocí binárních stromů, ale s tím zkušenosti nemám.

Metoda Boží mlýny

Toto je nejjednodušší postup. Označujeme si do pole hodnoty, které už byly použity. Pokud zjistíme, že jsme vytáhli už použitou hodnotu, tak losujeme znova. Zpočátku není problém, ale postupně se dostáváme do situace, kdy nám zbývají posledí tři, dvě, jedna hodnota a my pořád naslepo zkoušíme, zdali již byla tažena či ne. Pokud máme deset závodníků, tak u posledního závodníka máme pravděpodobnost jeho správného vylosování 1/10, t.j. 10%. Pokud je jich ale milión, tak pravděpodobnost úspěchu při posledním "tahu" je 1/1000000, t.j. 0,00001%. To opravdu není mnoho a běh algoritmu trvá dlouho. Na mém počítači 30 sekund. Toto řešení lze tedy snad se skřípěním zubů použít pokud je počet hodnot malý, ale při vetších počtech je už algoritmus neúnosný.
type RndEmitor = object
  pole:array [0..POCET-1] of longint;
  Procedure Init(n:longint);
  Function DejHodnotu:longint;
  Procedure Done;
  end;

Procedure RndEmitor.Init(n:longint);
var a:longint;
begin
randomize;
for a:=0 to POCET-1 do pole[a]:=0;
end;

Function RndEmitor.DejHodnotu:longint;
var a:longint;
begin
repeat
   a:=Random(POCET);
until pole[a]<>1;
pole[a]:=1;
DejHodnotu:=a;
end;

Metoda míchačka

Při této metodě během inicializace promícháme výchozí pole a pak při fázi výběru budeme jednoduše procházet pole od začátku do konce a číst uložené hodnoty. V podstatě provedeme algoritmus třídění naruby. Závodníky tedy nebudeme pouštět na start ad hoc, ale dopředu si připravíme jejich pořadník. Nevýhodu metody je patrná prodleva během inicializace, ale na druhou stranu, samotné generování hodnot je extrémně rychlé.
Otázka je, jak důkladně a jakým způsobem pole zamíchat.
type RndEmitor = object
  pole:array [0..POCET-1] of longint;
  ukazatel:longint;
  Procedure Init(n:longint);
  Function DejHodnotu:longint;
  Procedure Done;
  end;

Procedure RndEmitor.Init(n:longint);
var a,b,c,temp:longint;
begin
{1.faze}
randomize;
ukazatel:=0;
for a:=0 to POCET-1 do pole[a]:=a;

{2.faze}
for a:=0 to POCET div 3 do
    begin
    b:=Random(POCET);
    c:=Random(POCET);
    temp:=pole[b];
    pole[b]:=pole[c];
    pole[c]:=temp;
    end;
end;

Function RndEmitor.DejHodnotu:longint;
begin
DejHodnotu:=pole[ukazatel];
inc(ukazatel);
end;
Podívejte se na řádku, která je vytištěna tučně, t.j.: "for a:=0 to POCET div 3 do"
Ideální by patrně bylo "for a:=0 to POCET do", ale ukazuje se, že tak důkladné míchání není třeba. Mě se osvědčilo právě míchání na třetinu počtu hodnot. Pokud se míchá méně, tak je již patrné, že rozložení není zcela náhodné a napřed naskakují spíše nízká a později spíše vysoká čísla.

Metoda zkracování pole

Při této metodě si nesestavujeme „blacklist“ již použitých hodnot, ale naopak udržujeme „whitelist“ ještě použitelných hodnot. Lze použít různé implementace tohoto postupu. Níže je uvedena metoda zkracování pole. Z pole vybereme hodnotu a poté pole smrštíme tak, abychom „zacelili díru“ po této vyzobnuté hodnotě. Tím, jak zkracujeme pole, také zužujeme rozsah generátoru náhodných čísel.
Tato metoda je z důvodu neustálého kopírování velkých částí pole velmi, velmi pomalá, a proto ji lze použít jen na velice krátká pole.
type RndEmitor = object
  pole:array [0..POCET-1] of longint;
  ukazatel:longint;
  Procedure Init(n:longint);
  Function DejHodnotu:longint;
  Procedure Done;
  end;

Procedure RndEmitor.Init(n:longint);
var a,b,c,temp:longint;
begin
randomize;
ukazatel:=pocet;
for a:=0 to POCET-1 do pole[a]:=a;
end;

Function RndEmitor.DejHodnotu:longint;
var a,b:longint;
begin
a:=Random(ukazatel);
DejHodnotu:=pole[a];
for b:=a to ukazatel-2 do pole[b]:=pole[b+1];
dec(ukazatel);
end;

Metoda realtime míchačky

Poslední metoda v podstatě kombinuje whitelist a míchání pole. Toto míchání ale probíhá průběžně, nikoliv při inicializaci. Při generování zase čteme prvky pole, přitom použité hodnoty odklízíme nikoliv pomocí podouvání pole, ale jejich prohazováním s hodnotami v již projité části pole. Výhodou algoritmu je vysoká a konstantní rychlost.
type RndEmitor = object
  pole:array [0..POCET-1] of longint;
  zbyva:longint;
  Procedure Init(n:longint);
  Function DejHodnotu:longint;
  Procedure Done;
  end;

Procedure RndEmitor.Init(n:longint);
var a,b,c,temp:longint;
begin
randomize;
zbyva:=pocet;
for a:=0 to POCET-1 do pole[a]:=a;
end;


Function RndEmitor.DejHodnotu:longint;
var i,j,temp:longint;
begin
j:=POCET-zbyva;
i:=random(zbyva)+j;
temp:=pole[i];
pole[i]:=pole[j];
pole[j]:=temp;
dec(zbyva);
DejHodnotu:=temp;
end;



Pascal - hlavní
Překladače
Vlastní články
Převzaté články
Věci na stáhnutí
Odkazy k tématu
BP7 buglist
Chyba Run-time 200

BASIC