» 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


Genetika a příjmení: Unikátní možnost získat test Y-DNA zdarma a dozvědět se o svých předcích

Genetika a příjmení: Unikátní možnost získat test Y-DNA zdarma a dozvědět se o svých předcích

** Projekt Genetika a příjmení hledá shody mezi osobami se stejným příjmením ** Využívá k tomu testování DNA na chromozomu Y ** Výsledky testu můžete účastí v projektu získat zdarma

11.  1.  2018 | Marek Lutonský | 3

Pojďme programovat elektroniku: Z čeho poskládat venkovní meteosondu, která poběží celé roky

Pojďme programovat elektroniku: Z čeho poskládat venkovní meteosondu, která poběží celé roky

** Dnes si ukážeme, z čeho postavit venkovní meteosondu ** Tak, aby fungovala celé roky ** A posílala data třeba pomocí Wi-Fi

14.  1.  2018 | Jakub Čížek | 19


Aktuální číslo časopisu Computer

Zachraňte nefunkční Windows

Jak nakupovat a prodávat kryptoměny

Otestovali jsme konvertibilní notebooky

Velký test 14 herních myší