D'un a ena (4) P44612


Statement
 

pdf   zip

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

Per exemple, considereu la permutació (4,3,2,5,1,7,6)(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→11 \to 4 \to 5 \to 1 (té dos cicles més). En canvi, la permutació (3,4,5,6,7,1,2)(3,4,5,6,7,1,2) només té un cicle: 1→3→5→7→2→4→6→11 \to 3 \to 5 \to 7 \to 2 \to 4 \to 6 \to 1.

Per fer aquest problema més interessant, algunes de les posicions ja estaran fixades. Usarem nn 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>0n > 0 seguit dels nn valors per indicar les posicions fixades.

Sortida

Escriviu totes les permutacions de {1,2,…,n}\{ 1, 2, \dots, 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++