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
#1 25. 10. 2019 13:46
K-tá permutace
Ahoj,
mám problém s jedním příkladem na Algoritmizaci.
Zadání:
Jsou dána dvě přirozená čísla N a K. Hodnota K je z rozmezí od 1 do N!. Navrhněte efektivní algoritmus, jak nalézt v pořadí K-tou permutaci množiny čísel {1, 2, 3, ..., N} v lexikografickém uspořádání. Vypočtěte asymptotickou složitost algoritmu.
Děkuju za pomoc
Offline
- (téma jako vyřešené označil(a) Alesekk)
#2 25. 10. 2019 15:36
- check_drummer
- Příspěvky: 4892
- Reputace: 105
Re: K-tá permutace
↑ Alesekk:
Ahoj, kolik permutací má na prvním místě číslo i? Z odpovědi na tuto otázku by už mohlo být možné postup sestavit...
"Máte úhel beta." "No to nemám."
Offline
#3 25. 10. 2019 16:09 — Editoval Alesekk (25. 10. 2019 17:25)
Re: K-tá permutace
↑ check_drummer:
Já jsem přišel na to, jak spočítat první číslo permutace, 
Dále mě napadlo, že výsledný algoritmus by mohl pracovat se zbytkem po dělení právě tohoto výrazu +1. Akorát nevím, jak "zpracovat" tento výsledek po dělení, aby mi následující čísla dávaly smysl.
Díky za odpověď.
Offline
#4 26. 10. 2019 13:53
- check_drummer
- Příspěvky: 4892
- Reputace: 105
Re: K-tá permutace
↑ Alesekk:
Vypadá to dobře, jen by tam měla být asi dolní celá část, tj.
No a pak musíš zmenšit K na 
, to jsi asi myslel. A dál postupuješ stejně (rekurzí), jen použiješ novou hodnotu K a n-1. A co je důležité, nepermutuješ už čísla 1,..,n, ale n-1 čísel, ze kterých vyhodíš číslo, které jsi získal v předchozím kroku pomocí toho vzorce výše. Také až ti v dalším kroku vyjde výsledek i, tak to neznamná číslo i, ale i-té číslo ve tvém seznamu.
"Máte úhel beta." "No to nemám."
Offline