» Poradna » Programy

[algoritmus] Jak najit n-tou permutaci?

 |   |   |  [81.0.194.---]

Zdravim,

Mam za ukol napsat program, ktery bude delat toto:

na vstupu dostane retezec, v nemz se MUZOU OPAKOVAT ZNAKY; a cislo n
na vystupu ma vypsat n-tou permutaci z techto znaku. Permutace jsou razene podle abecedy.

Snad je to pochopitelne, radeji ale uvedu nejake priklady:
VSTUP: VYSTUP
abca 1: aabc
abca 2: aacb
abca 3: abac
abca 4: abca
baaaa 1: aaaab
baaaa 2: aaaba
baaaa 5: baaaa
baaaa 6: neexistuje

Pujde to nejak jinak nez hrubou silou? Prochazet od zacatku vsechny mozne permutace se mi nezda moc efektivni. Preci jenom ta narocnost algoritmu na hledani dalsi permutace taky neni zrovna mala.

Moc napadu zatim nemam, jediny kandidat je prochazet postupne ten retezec odzadu a hledat pocet permutaci jeho podretezcu, coz neni tezke (n faktorial/ soucin faktorialu poctu opakujicich se znaku) a jakmile to cislo preleze pozadovane cislo tak najit tu permutaci. Asi by to tak slo, ale neni to ono.

Kdybyste nekdo meli jakykoliv napad, budu vam vdecen.

Dekuji.


Související témata: Algoritmus



Určitě si přečtěte


Tesla chce změnit nákladní dopravu. Její elektrický náklaďák má ohromující parametry

Tesla chce změnit nákladní dopravu. Její elektrický náklaďák má ohromující parametry

** Tesla představila elektrický kamion ** Má obdivuhodný výkon i dojezd ** Prodávat by se měl už za dva roky

17.  11.  2017 | Vojtěch Malý | 226

Nejlepší notebooky do 10 tisíc, které si teď můžete koupit

Nejlepší notebooky do 10 tisíc, které si teď můžete koupit

** I pod hranicí desíti tisíc korun existují dobře použitelné notebooky ** Mohou plnit roli pracovního stroje i zařízení pro zábavu ** Nejlevnější použitelný notebook koupíte za pět a půl tisíce

16.  11.  2017 | Stanislav Janů | 53

Do 20 let nebude nikdo vlastnit auta, říká zkušený šéf několika automobilek

Do 20 let nebude nikdo vlastnit auta, říká zkušený šéf několika automobilek

** Bývalý šéf a expert z několika velkých automobilek se vyjádřil k budoucnosti tohoto průmyslu ** Do 20 let „nikdo“ nebude vlastnit auta ** Veškerá doprava bude řešená pomocí velkých logistických platforem

15.  11.  2017 | Karel Javůrek | 74


Aktuální číslo časopisu Computer

Otestovali jsme 5 HDR 4K televizorů

Jak natáčet video zrcadlovkou

Vytvořte si chytrou domácnost

Radíme s koupí počítačového zdroje