Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#2 22. 11. 2009 23:10
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: N-tá permutace
Asi myslíš m-tou permutaci z 1...n (pokud má být opravdu n-tá, tak stačí dosadit za m=n)
Jak na to? Rekurzivně. Položme k=((m-1) div (n-1)!)+1, l=((m-1) mod (n-1)!)+1. Vypíšeme číslo m následovanlé l-tou permutací množiny {1,...,k-1,k+1,...,n}. Protože takto množinu, z níž bereme permutaci, zmenšujeme, dojde rekurze do konce.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#3 23. 11. 2009 16:50
Re: N-tá permutace
Já si to zrekapituluju:
Dostanu dvě čísla, jedno udává pořadí permutace (např. n=34) a druhé udává permutaci 1...n (tedy např. n=5).
Teď tedy:
vypočtu k,l:
k=33div4!+1=2
l=33mod4!+1=10
teď vypíšu číslo k(jakožto první číslo hledané permutace);
do m si uložím hodnotu l(tedy 10) a a do n hodnotu(4)-protože teď když jsem už našel první číslo, hledám permutaci, která má o jeden míň prvků.
Znovu si vypočtu k,l: k=9div3!+1=2(ale 2 už mám na prvním místě, takže si vezmu číslo o 1 větší(???) tedy 3??
l=9 mod3!+1=4.
opět si do m uložím hodnotu l a do n hodnotu 3 a takto postupuji až do doby kdy budu mít n=1.
Postupuji správně? Obávám se že ne, protže např. pro m=8 a n=4 mi to najde permutaci 2134 a já bych potřeboval 2143. Je to tím, že dělám špatně krok kdy jsem o 1 zvětšil číslo které už bylo v permutaci?
Díky
Offline
#4 23. 11. 2009 17:33
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: N-tá permutace
↑ Torpy:
Zbastlil jsem to v haskellu:
Code:
fact 0 = 1
fact i = i*fact(i-1)
nthpermx _ []=[]
nthpermx m x=p:nthpermx (1+mod (m-1) f) (filter (/=p) x)
where f=fact(length(x)-1); p=x !! (div (m-1) f)
nthperm m n = nthpermx m [1..n]Rozdíl proti tvému slovnímu popisu je v tom, že si musíme udržovat mnžinu čísel, která ještě lze v permutaci použít.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#8 11. 12. 2009 17:23
Re: N-tá permutace
Diky moc za radu, ale kedze som uplny noob, tak mi to nejak nejde, snazil som sa to nejak napasovat do pascalu ale nevychadza mi to, mohli by ste mi niekto vysvetlit hlbsie ten princip ako funguje vypocet tej permutacie, poprosil by som vysvetlenie ako pre uplne veci neznaleho.
dakujem
Offline