Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Direktno izracunavanje i-te varijacije skupa

[es] :: Art of Programming :: Direktno izracunavanje i-te varijacije skupa

[ Pregleda: 2410 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor
Pretraga teme: Traži
Markiranje Štampanje RSS

Igor Gajic

Član broj: 93194
Poruke: 747
62.193.143.*



+987 Profil

icon Direktno izracunavanje i-te varijacije skupa07.12.2006. u 17:08 - pre 211 meseci


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.
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
89.190.198.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Direktno izracunavanje i-te varijacije skupa10.12.2006. u 08:19 - pre 211 meseci
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.
Ipak se ++uje.
 
Odgovor na temu

Igor Gajic

Član broj: 93194
Poruke: 747
62.193.143.*



+987 Profil

icon Re: Direktno izracunavanje i-te varijacije skupa10.12.2006. u 12:29 - pre 211 meseci
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.
 
Odgovor na temu

[es] :: Art of Programming :: Direktno izracunavanje i-te varijacije skupa

[ Pregleda: 2410 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.