# ADS úlohy E - prank

Permutaci čísel zde budu označovat jako řetězec.
Je-li na posledních $p$ pozicích řetězce rostoucí posloupnost, pak prvek těsně před touto posloupností se změní až v $p!$-té následující permutaci. Aby se totiž na pozicích od $n-p$ do $n-1$ (indexuji od nuly) změnila posloupnost na klesající, budou se muset vystřídat všechny permutace na těchto pozicích - od lexikograficky první do lexikograficky poslední.

Jak toto pomůže při sestavování dané permutace? Příklad (pořadí, řetězec):

$0: 123$
$1: 132$
$2: 213$
$3: 231$
$4: 312$
$5: 321$

Zaměřím se na permutaci 3:
Začínám-li dvojkou, pak to signalizuje, že se muselo na zbývajících pozicích protočit $1*2!$ permutací. Proč: $"1"$ znamená, že dvojka se nachází o $1$ pozici za jedničkou, a $2!$ znamená, že prvky na zbývajících dvou pozicích tvoří $2!$ permutací.
Trojka na druhé pozici znamená protočení $1*1!$ permutací - trojka je nyní o jeden krok za jedničkou, jelikož dvojku už jsem použil. To vede na následující myšlenku:

Představím si, že mám řetězec $123$ a z něj postupně odebírám prvky, abych dostal příslušnou permutaci. Pak indexy, které ukazují na pozice odebíraných prvků, budou následující:

$0: 000$
$1: 010$
$2: 100$
$3: 110$
$4: 200$
$5: 210$

což jsou příslušné násobky faktoriálů - např. $3=1*2!+1*1!+0*0!$.
Toto mi pomůže zjistit, jak z permutace zjistit její pořadí

## Algoritmus:
Například pro permutaci 24153 postupuji následovně (oba postupy zdůvodním později):
### Z tvaru permutace do čísla

1. Setřídím výchozí posloupnost
$12345$
3. Odebírám prvky tak, abych opět vytvořil příslušnou posloupnost, a u každého prvku si poznačím index:
$2: 1345, 1$
$4: 135, 2$
$1: 35, 0$
$5: 3, 1$
$3: NIL, 0$
3. Jednotlivé koeficienty vynásobím příslušným faktoriálem, počínaje $(n-1)!$:
$1*4!=24$
$2*3!=12$
$0*2!=0$
$1*1!=1$
$0*0!=0$
4. Posčítám (a přičtu $1$, je-li permutace č. $1$ brána jako první)
$24+12+0+1+1=38$

Obrácený postup - z čísla vyčíst tvar permutace - probíhá následovně:

### Z čísla do tvaru permutace

1. (Od čísla permutace odečtu $1$.) Dělím číslo permutace koeficienty od $1$ do $n$ a zapisuji si zbytky:
$37/1 = 37;0$
$37/2 = 18;1$
$18/3 = 6;0$
$6/4 = 1;2$
$1/5 = 0;1$
2. Vezmu si setříděnou posloupnost $1\dots n$
$12345$
3. Čtu zbytky v obráceném pořadí. Prvek s příslušným indexem odeberu z posloupnosti a přidám do řetězce:
$1: 2, 1345$
$2: 24, 135$
$0: 241, 35$
$1: 2415, 3$
$0: 24153, NIL$

## Zdůvodnění, důkaz

### Proč faktoriál

Mám-li na $k$-tou pozici zprava umístit číslo, které je momentálně $s$-té v pořadí, musí se napravo od této pozice protočit $(s-1)*(k-1)!$ permutací. Například dvojka na první pozici (pro pět prvků) vyžaduje protočení 24 permutací na posledních 4 pozicích - prvních 24 permutací totiž obsahuje jedničku na první pozici. Poslední prvek bude vždy vyžadovat $0*0!$ permutací, jelikož jediný zbývá v zásobě.

### Převod mezi indexy a číslem permutace

Mezi "kódem" (vybíráním indexů) a číslem permutace existuje vzájemná bijekce. Snadněji toto lze vidět v případě, kdy by se nejednalo o permutace, ale o variace s opakováním. Na prvním místě bych mohl zvolit $n$ čísel, na druhém místě $n$ čísel... celkem tak $n^n$ různých variací. Převod mezi kódem a číslem permutace by tak fungoval jako Hornerovo schéma pro pětkovou soustavu. Obdobný algoritmus lze použít i v tomto případě, počet možných číslic se však liší od různé pozice - a tedy i činitel/dělitel.

Srovnání: pětková soustava oproti soustavě permutací pěti prvků:

Index $0$: $5^4$ vs $4!$
Index $1$: $5^3$ vs $3!$
...
Index $4$: $5^0$ vs $0!$

Maximální číslo permutace je $5!-1$ (jelikož existuje $5!$ permutací) - podobně jako největší čtyřciferné číslo pětkové soustavy je $5^5-1=3124=4444_5$.
Z těchto důvodů lze pro zjištění vybraných indexů použít obdobné algoritmy.