Matematické Fórum

terry · 04. 05. 2009 18:18 — Editoval terry (04. 05. 2009 18:31)

ahoj, máme tento úkol na seminář programování a já si s tím vůbec nevím rady, mohl by mi s tim někdo pomoc.. dík

Následující permutace
Na standardním vstupu je dáno nejprve jedno kladné celé číslo N, které není větší než 100. Následuje permutace množiny přirozených čísel {1, 2, ..., N}, přičemž jednotlivá čísla jsou na vstupu od sebe oddělena mezerami. Všechny vstupní údaje jsou umístěny na jednom řádku.
Program k zadané permutaci určí permutaci bezprostředně po ní následující v lexikografickém uspořádání. Výslednou permutaci vypíše do jednoho řádku na standardní výstup, její jednotlivé členy budou na výstupu opět odděleny mezerami. Pokud byla zadána poslední permutace v lexikogafickém uspořádání a následující permutace tedy neexistuje, program vypíše pouze znakový řetězec NEEXISTUJE a skončí.

Příklad vstupu:
6 1 3 6 2 5 4

Odpovídající správný výstup:
1 3 6 4 2 5

Kondr · 04. 05. 2009 19:25

Abychom permutaci lexikograficky zvětšili jenom o trochu, budeme se sanžit dělt změnu co nejvíc na konci. A protože ji chceme zvětšit, znamená to, že první (bráno zleva) položka, kterou změním, musí být zvětšena. Proto pokud je konec permutace klesající, prohozením dvou prvků permutaci naopak znížíme. Pokud je klesající celá permutace, je lexikograficky největší.

Stačí posloupnost projít od konce a zjistit, jaká část je klesající. Pokudcelá permutace, vypíšeme NEEXISTUJE. Předpokládejme nyní, že je klesající pouze část, viz příklad:
1,4,2,6,5,3
po ní má násedovat
1,4,3,2,5,6
jak jsme to vyrobili: odsekli jsme klesající knec a jeden znak navíc. Zbylo nám 1,4, to jsme opsali na výstup. Místo dvojky použijeme to číslo z klesajícího konce, které je vzhledem ke dvojce nejbližší vyšší. To vypíšeme na výstup. Do zbytku původně klesajícího konce zařadíme dvojku a tento konec vypíšeme v rostoucím pořadí.

Jinak je na to funkce v STL: http://marknelson.us/2002/03/01/next-permutation

Matematické Fórum

#1 04. 05. 2009 18:18 — Editoval terry (04. 05. 2009 18:31)

algoritmus - následující permutace

#2 04. 05. 2009 19:25

Re: algoritmus - následující permutace

Zápatí