D'un a ena (4) P44612

Statement

html

Feu un programa que escrigui totes les permutacions de { 1, …, n } amb un cicle exactament. Suposeu que el contingut de la posició i indica “la següent posició que cal visitar”.

Per exemple, considereu la permutació (4,3,2,5,1,7,6). A la posició 1 hi ha un 4, a la posició 4 hi ha un 5, i a la posició 5 hi ha un 1. Així doncs, un dels cicles d’aquesta permutació és 1 → 4 → 5 → 1 (té dos cicles més). En canvi, la permutació (3,4,5,6,7,1,2) només té un cicle: 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Per fer aquest problema més interessant, algunes de les posicions ja estaran fixades. Usarem n valors per indicar-ho: les posicions lliures tindran un 0, i les altres el valor ja fixat.

Entrada

L’entrada consisteix en un natural n > 0 seguit dels n valors per indicar les posicions fixades.

Sortida

Escriviu totes les permutacions de { 1, 2, …, n } amb un únic cicle que tenen les posicions fixades donades. Sempre hi haurà almenys una solució.

Informació sobre el corrector

Podeu escriure les solucions d’aquest exercici en qualsevol ordre.

Public test cases

Input

1
0

Output

(1)

Input

3
0 0 0

Output

(2,3,1)
(3,1,2)

Input

6
4 0 6 0 0 0

Output

(4,3,6,2,1,5)
(4,5,6,2,3,1)
(4,5,6,3,1,2)
(4,1,6,3,2,5)
(4,3,6,5,2,1)
(4,1,6,5,3,2)

Input

7
3 4 0 6 0 1 2

Output

(3,4,5,6,7,1,2)

Information

Author: Salvador Roura
Language: Catalan
Other languages: Spanish
Official solutions: C++
User solutions: C++