#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: 5578
- Reputace: 106
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: 5578
- Reputace: 106
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