Posted By: snake (Keeping on the sunny side) on 'CZprogram'
Title:     Re: Permutace
Date:      Wed Jun 25 00:07:04 2003

Na zacatek:

v cem to potrebujes? je to vymyslene pro kterykoli programovaci jazyk a je to
uloha, ktera se dava prvakum, aby ji naprogramovali v ramci 2 hodin vcetne
odladeni:-)...

No a dalsi poznamky: pokud to potrebujes spustit na 16, spocital jsi si, kolik 
vychazi "16!"? Je to 20 922 789 888 000, coz jsou biliony... Takze na 
normalnim procesoru se do roka nedopocitas. Posledni poznamka: pokud to ma vic 
reseni a Ty chces najit jenom jedno z nich, bude rozumnejsi asi vymyslet jiny 
postup, mohou to byt treba geneticke algoritmy... No a v nejposlednejsi rade 
dost zalezi na tom, jestli se cleny opakuji ci neopakuji... 

No a ted v kratkosti postup prohledavani pro n-faktorial:
rekurze (k=kolikata_cislice)
  - n = k+1 ? vypis permutaci; jinak
  - dej na k-tou pozici postupne cislici na k-te az n-te pozici a zavolej
    rekurzi (k+1); k-tou az n-tou pozici jde vytvorit bez dodatecnych
    promennych, staci vzdycky prohazovat dvojice, pokud ty permutace 
    nepotrebujes mit vzestupne serazene (prvni se zavola rekurze(k+1), pak
    se prohodi k. a k+1. clen a zavola rekurze, pak k. a k+2. a a...)

Vola se to samozrejme rekurze(1).

snake

>   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;)