Posted By: Rat (prilis mnoho her) on 'CZprogram' Title: Re: Permutacey Date: Wed Jun 25 13:30:28 2003 > Ahoj. > > Chci prohledavat do sirky reseni jednoho hlavolamu a prisel jsem, jak > pozice > hlavolamu zakodovat do cisla. Z cisla vyrobim pozici, tu pak je ohodnotim a > kdyz to pustim pres noc, tak urcite najdu nejlepsi reseni:) > > Abych to alespon trochu urychlil, tak jsem zjistil, ze pozice hry nejsou > vsechna cisla, ale jen permutace. Napriklad pro delku cislice rovnu 3: > > 123 > 132 > 213 > 231 > 312 > 321 > > V klidku to muzu pustit na vsechna trojciferna cisla,ale dovedete si > predstavit ten bugr, kdyz bych to pustil na 16timistne cislo;) > > Muj problem: Nevite o nejakem optimalnim algoritmu generujicim permutace > daneho retezce? Pokud mozno bez rekurze;-) Bud nechapu zadani nebo: ??? To jsem snad psal, jako priklad na zkousce v prvnim semestru... i se zjistenim poradi a naopak vygenerovanim permutace z poradi v linearnim zavislosti na jeji delce. Jedes od konce a hledas, cim nahradit posledni index. To se ti samozrejme nepovede, takze ho uvolnis a snazis se zvysit predchozi, dokud na takovy nenarazis, pak ho zvysis a zbytek vzestupne obsadis uvolnenymi indexy. Paklize mas nejake lockle, tak je jednoduse preskaces (pocitas s nima jako obsazenyma, ale nesmis se je pokusit zvysovat a uvolnovat). Tolik asi, co me ted napadlo z hlavy, mozna to pujde trosku zoptimalizovat... > Diky za napady i prakticke rady. > Jovo. Krysa rat@atrey.karlin.mff.cuni.cz Jsem Krysa http://atrey.karlin.mff.cuni.cz/~rat/