[ kgstefan88 @ 04.01.2011. 22:23 ] @
Zdravo, resavam neki problem i potreban mi je algoritam da nadjem
x-tu varijaciju reda n sa n. (valjda se ovako kaze)

znaci imam n brojeva, i trebam da ih rasporedim na n mesta tako da se nijedan broj ne ponavlja.


npr.
n=8

ukupno ima 8! tj. 8*7*6*5*4*3*2*1 varijacija

redom oznacavam varijacije sa

0. 0 1 2 3 4 5 6
1. 0 1 2 3 4 6 5
2. 0 1 2 3 5 4 6
3. 0 1 2 3 5 6 4
4. 0 1 2 3 6 4 5
5. 0 1 2 3 6 5 4
.
.
.
n!-1 6 5 4 3 2 1 0

Ne bih da iznosim svoju ideju da ne bih nekog navukao na tu stranu. Ako uspem nesto da uradim okacicu resenje, takodje ako neko uspe da uradi nesto da uradi nek okaci.

Unapred hvala


p.s. Rekurzivno resenje mi ne pije vodu, jer radim paralelno programiranje i ne sme jedan proces da ceka da sledeci zavrsi izracunavanje.
[ Mihajlo Cvetanović @ 05.01.2011. 10:38 ] @
Da li ti baš treba permutacija pod nekim zadatim rednim brojem, ili ti treba sledeća permutacija ako imaš postojeću? Da li baš radiš u C-u ili radiš u C++? Ako je na oba pitanja odgovor druga opcija onda već postoji funkcija koja to radi, next_permutation

Inače, računanje permutacije iz rednog broja iste bi verovatno najbrže išlo tako što bi od broja oduzimao sve manje faktorijele prilikom određivanja sledećeg elementa, sve do kraja. Tja, opet mi je lakše da nacrtam:

n=8, n!=40320
Code:
    0: 0 1 2 3 4 5 6 7
...
40319: 7 6 5 4 3 2 1 0

i = 10000 = 1 * 7! + 6 * 6! + 5 * 5! + 1 * 4! + 2 * 3! + 2 * 2! + 0 * 1!
Code:
10000: 1 (0 2 3 4 5 6 7)
       7 (0 2 3 4 5 6)
       6 (0 2 3 4 5)
       2 (0 3 4 5)
       4 (0 3 5)
       5 (0 3)
       0 (3)
       3

to jest, 10000: 1 7 6 2 4 5 0 3