Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

random index

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
ime
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 06. 2009. (12:39:51)
Postovi: (2)16
Sarma = la pohva - posuda
0 = 0 - 0
PostPostano: 13:00 sub, 13. 6. 2009    Naslov: random index Citirajte i odgovorite
pozdrav, evo moj prvi post ovdje. (inace ne idem na ovaj faks)
ako moze tko mi objasnit ovaj dolje algoritam. ovaj forum izgleda kao pravo mjesto da postavim ovo pitanje.

recimo da imam u skupu S niz brojeva.
brojevi su po redosljedu od 0 do MaxBroj (koji je power of 2)

algoritam koji generira random brojeve MaxBroj puta , ali takav da ce svaki broj iz skupa S generirati jedanput (pokriti sve brojeve):
[code:1] private List<int> RandomIndex(int MaxBroj)
{
int a, b;
List<int> generated = new List<int>();

int InitialValue = Random(MaxBroj);

a = Random(MaxBroj);
b = InitialValue;

do
{
generated.Add(a ^ b);
a += Random(MaxBroj) & -2;
a = a % MaxBroj;
b++;
b = b % MaxBroj;
} while (b != InitialValue);
return generated;
}
[/code:1](^ - XOR, & - AND, % - MOD)

na koju foru radi algoritam ? (zasto radi to sto radi?)
hvala unaprijed.
pozdrav, evo moj prvi post ovdje. (inace ne idem na ovaj faks)
ako moze tko mi objasnit ovaj dolje algoritam. ovaj forum izgleda kao pravo mjesto da postavim ovo pitanje.

recimo da imam u skupu S niz brojeva.
brojevi su po redosljedu od 0 do MaxBroj (koji je power of 2)

algoritam koji generira random brojeve MaxBroj puta , ali takav da ce svaki broj iz skupa S generirati jedanput (pokriti sve brojeve):
Kod:
        private List<int> RandomIndex(int MaxBroj)
        {
            int a, b;
            List<int> generated = new List<int>();

            int InitialValue = Random(MaxBroj);

            a = Random(MaxBroj);
            b = InitialValue;

            do
            {
                generated.Add(a ^ b);
                a += Random(MaxBroj) & -2;
                a = a % MaxBroj;
                b++;
                b = b % MaxBroj;
            } while (b != InitialValue);
            return generated;
        }
(^ - XOR, & - AND, % - MOD)

na koju foru radi algoritam ? (zasto radi to sto radi?)
hvala unaprijed.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Mad Wilson
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 29. 05. 2006. (22:51:14)
Postovi: (121)16
Sarma = la pohva - posuda
23 = 34 - 11
PostPostano: 21:24 ned, 14. 6. 2009    Naslov: Citirajte i odgovorite
Hmm.... cini se da je ideja da se izvrte sve premutacije znamenaka brojeva u skupu (u bazi 2). Varijabla [b]b[/b] bi trebala jamciti da se generirani brojevi nece ponavljati, jer se uzima [tt]xor[/tt] izmedju nje i random broja. Tu je jasno da se broj moze ponoviti u tocno jednom slucaju: ako [b]a[/b] poprimi vrijednost koju je prije imala [b]b[/b] i obratno (ako zamjene vrijednosti). O tome bi trebala brinuti linija [tt]a += Random(MaxBroj) & -2; [/tt], ali ne bih rekao da brine: primjer - neka je MaxBroj = 8
[code:1]
------- inicijalni random brojevi su 0 za InitValue i 4 za a:
a=100
b=000
------- random broj je 2
a=110
b=001
------- random broj je 5 (ali se zbog &-2 gleda kao 4)
a=010
b=010
------- random broj je 6
a=000
b=011
------- random broj je 0 (opet)
a=000
b=100
-------
[/code:1]
Imam li gresku?

EDIT: Upravo sam isprobao i cini se da doista ne radi; preporucujem drugu strategiju. Na pocetku listu napuni brojevima od 0 do MaxBroj-1 ([tt]0 1 2 3 4 5 6 7[/tt]). Zatim uzimaj jedan po jedan index iz liste i nasumce biraj gdje ces ga smjestiti. Dakle, prvo uzmemo 7micu. Gdje cemo nju smjestiti? Uzmemo Random(MaxBroj) i smjestimo ju na taj index tj. swapamo broj koji se nalazi na tom indexu sa nasom sedmicom. Nakon toga gledajmo gdje cemo smjestiti broj na indexu 6 (koji mozda vise nije 6). Njega cemo smjestiti na Random([color=red]MaxBroj-1[/color]). Broj na indexu 5 swapamo sa elementom na indexu Random([color=red]MaxBroj-2[/color]) i dalje redom.

[code:1]
0 1 2 3 4 5 6 7
| (trazimo random broj do MaxBroj : rasporedujemo zadnji element)
* (odabrano mjesto)
----------------
0 1 2 7 4 5 6 3
| (trazimo random broj do MaxBroj-1 : rasporedujemo predzadnji element)
* (odabrano mjesto)
----------------
0 6 2 7 4 5 1 3
| (trazimo random broj do MaxBroj-2) : rasporedujemo predpredzadnji element
* (odabrano mjesto)
----------------
- - -
- - -
[/code:1]

Mislim da nam ovaj postupak generira ispunjenje uvjeta.
Hmm.... cini se da je ideja da se izvrte sve premutacije znamenaka brojeva u skupu (u bazi 2). Varijabla b bi trebala jamciti da se generirani brojevi nece ponavljati, jer se uzima xor izmedju nje i random broja. Tu je jasno da se broj moze ponoviti u tocno jednom slucaju: ako a poprimi vrijednost koju je prije imala b i obratno (ako zamjene vrijednosti). O tome bi trebala brinuti linija a += Random(MaxBroj) & -2; , ali ne bih rekao da brine: primjer - neka je MaxBroj = 8
Kod:

------- inicijalni random brojevi su 0 za InitValue i 4 za a:
a=100
b=000
------- random broj je 2
a=110
b=001
------- random broj je 5 (ali se zbog &-2 gleda kao 4)
a=010
b=010
------- random broj je 6
a=000
b=011
------- random broj je 0 (opet)
a=000
b=100
-------

Imam li gresku?

EDIT: Upravo sam isprobao i cini se da doista ne radi; preporucujem drugu strategiju. Na pocetku listu napuni brojevima od 0 do MaxBroj-1 (0 1 2 3 4 5 6 7). Zatim uzimaj jedan po jedan index iz liste i nasumce biraj gdje ces ga smjestiti. Dakle, prvo uzmemo 7micu. Gdje cemo nju smjestiti? Uzmemo Random(MaxBroj) i smjestimo ju na taj index tj. swapamo broj koji se nalazi na tom indexu sa nasom sedmicom. Nakon toga gledajmo gdje cemo smjestiti broj na indexu 6 (koji mozda vise nije 6). Njega cemo smjestiti na Random(MaxBroj-1). Broj na indexu 5 swapamo sa elementom na indexu Random(MaxBroj-2) i dalje redom.

Kod:

0 1 2 3 4 5 6 7
              | (trazimo random broj do MaxBroj : rasporedujemo zadnji element)
      *        (odabrano mjesto)
----------------
0 1 2 7 4 5 6 3
            | (trazimo random broj do MaxBroj-1 : rasporedujemo predzadnji element)
  *             (odabrano mjesto)
----------------
0 6 2 7 4 5 1 3
          | (trazimo random broj do MaxBroj-2) : rasporedujemo predpredzadnji element
    *            (odabrano mjesto)
----------------
  - - -
  - - -


Mislim da nam ovaj postupak generira ispunjenje uvjeta.



_________________
1 2 3 4

Zadnja promjena: Mad Wilson; 8:10 pon, 15. 6. 2009; ukupno mijenjano 2 put/a.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init
PostPostano: 22:19 ned, 14. 6. 2009    Naslov: Citirajte i odgovorite
Tocno to je linearni algoritam za potpune deranzmane. 8)
Tocno to je linearni algoritam za potpune deranzmane. Cool



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
ime
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 06. 2009. (12:39:51)
Postovi: (2)16
Sarma = la pohva - posuda
0 = 0 - 0
PostPostano: 17:20 pon, 15. 6. 2009    Naslov: Citirajte i odgovorite
[quote="Mad Wilson"]EDIT: Upravo sam isprobao i cini se da doista ne radi; [/quote]to mi nije palo na pamet :-)

[quote]preporucujem drugu strategiju...[/quote]ako sam dobro skuzio ta strategija bi zahtijevala da imam u memoriji listu brojeva sto mi bash i ne odgovara. znash nesto u gornjem stilu ali da radi u svim slucajevima? counter b. kao i gore ali da se na neku foru pretvori u unique random number unutar granica.
Mad Wilson (napisa):
EDIT: Upravo sam isprobao i cini se da doista ne radi;
to mi nije palo na pamet :-)

Citat:
preporucujem drugu strategiju...
ako sam dobro skuzio ta strategija bi zahtijevala da imam u memoriji listu brojeva sto mi bash i ne odgovara. znash nesto u gornjem stilu ali da radi u svim slucajevima? counter b. kao i gore ali da se na neku foru pretvori u unique random number unutar granica.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Mad Wilson
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 29. 05. 2006. (22:51:14)
Postovi: (121)16
Sarma = la pohva - posuda
23 = 34 - 11
PostPostano: 11:02 uto, 16. 6. 2009    Naslov: Citirajte i odgovorite
[quote="ime"]ako sam dobro skuzio ta strategija bi zahtijevala da imam u memoriji listu brojeva sto mi bash i ne odgovara. znash nesto u gornjem stilu ali da radi u svim slucajevima? counter b. kao i gore ali da se na neku foru pretvori u unique random number unutar granica.[/quote]

Hmm... ne znam, mozda probaj napraviti svoj generator slucajnih brojeva. Generatori slucajnih brojeva u principu rade obilnim koristenjem operatora modulo (sto ce reci generiraju ciklicku grupu jednaku skupu S gdje je seed generator - ako se dobro sjecam algebarskih ;) ). Tako je najjednostavnija funkcija generatora slucajnih brojeva [tt]x=(x+g)%MaxBroj[/tt], pri cemu bi [b]g[/b] trebao biti relativno prost u odnosu na [b]MaxBroj[/b].
ime (napisa):
ako sam dobro skuzio ta strategija bi zahtijevala da imam u memoriji listu brojeva sto mi bash i ne odgovara. znash nesto u gornjem stilu ali da radi u svim slucajevima? counter b. kao i gore ali da se na neku foru pretvori u unique random number unutar granica.


Hmm... ne znam, mozda probaj napraviti svoj generator slucajnih brojeva. Generatori slucajnih brojeva u principu rade obilnim koristenjem operatora modulo (sto ce reci generiraju ciklicku grupu jednaku skupu S gdje je seed generator - ako se dobro sjecam algebarskih Wink ). Tako je najjednostavnija funkcija generatora slucajnih brojeva x=(x+g)%MaxBroj, pri cemu bi g trebao biti relativno prost u odnosu na MaxBroj.



_________________
1 2 3 4
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan