[ 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. |