[ Igor Gajic @ 07.12.2006. 17:08 ] @


Neka je dat skup A={1,2,3,4,5}. Potrebno je izracunati i-tu varijaciju od 3 elemena skupa A,
koristeci samo broj varijacije tj. i, eventualno jos neke konstante, bez koriscenja skupovnih operacija.
Dakle algoritam bi trebao da bude slozenosti O(1), eventualno O(n).

Za ovaj primer varijacije od 3 elementa bi bile:
0. (1 2 3)
1. (1 2 4)
2. (1 2 5)
3. (1 3 1)
.
.
.
26.(3 1 2)
27. (3 1 4)
.
.
.


Moja ideja za prvi clan varijacije je sledeca:
Fiksiramo samo jedan elemenat, npr.
(1 X X)

Sada na mestu X X moze samo da bude 4 elementa tj. {2,3,4,5}.
I ima ukupno 12 varijacija od 4 elementa na 2 mesta.
Prema tome prvi clan varijacije bi mogao lako da se izracuna kao
Prvi=i/12;

Problem je kako odrediti ostala dva clana i-te varijacije.
[ Mali Misha @ 10.12.2006. 08:19 ] @
Citat:
0. (1 2 3)
1. (1 2 4)
2. (1 2 5)
3. (1 3 1)

Da ne misliš možda (kod 3.) na 1,3,2? U dnu posta opisuješ varijacije bez ponavljanja.
[ Igor Gajic @ 10.12.2006. 12:29 ] @
Citat:

Da ne misliš možda (kod 3.) na 1,3,2? U dnu posta opisuješ varijacije bez ponavljanja.



Lapsus calami.



Inace pisem f-ju u C#-u, pa skup A predstavljam kao niz A[0]=1;A[1]=2;A[2]=3....

Na ovaj nacin prvi element se moze predstaviti kao:

Prvi=A[i/12];


Pokusavao sam drugi da predstavim kao:


i%=12;
tmp=i/3;
if(A[tmp]==Prvi) tmp++;
Drugi=A[tmp];


Posto ima ukupno 12 kombinacija koje pocinju sa npr. 1,
trazi se ostatak i,tj.broja iteracija, pri deljenju sa 12.
Sada, ima po 3 varijacije koje pocinju sa 2, sa 3, sa 4, sa 5.
Stoga delim dobijeni broj sa 3 i pogledam da li se taj
broj nalazi na prvom mjestu, ako jeste trazim sledec clan.


Ovakav pristup radi u prvi 15-20 kombinacija, a posle pocinje ozbiljno da gresi.

Cini mi se da je dobar pristup ali nikako da ga nateram da radi.