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/

Search the boards