De uno a ene (4) P44612


Statement
 

pdf   zip

thehtml

Haced un programa que escriba las permutaciones de { 1, …, n } con un ciclo exactamente. Suponed que el contenido de la posición ‍i indica “la siguiente posición que hay que visitar”.

Por ejemplo, considerad la permutación (4,3,2,5,1,7,6). En la posición 1 hay un 4, en la posición 4 hay un 5, y en la 5 hay un 1. Así pues, uno de los ciclos de esta permutación es 1 → 4 → 5 → 1 (tiene dos ciclos más). En canvio, la permutación (3,4,5,6,7,1,2) sólo tiene un ciclo: 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Para hacer el problema más interesante, algunas posiciones ya estarán fijadas. Usaremos n ‍valores para indicarlo: las posiciones libres tendrán un 0, y las otras el valor ya fijado.

Entrada

La entrada consiste en un natural n > 0 seguido de los n valores para las posiciones fijadas.

Salida

Escribid todas las permutaciones de { 1, …, n } con un único ciclo que tienen las posiciones fijadas dadas. Siempre habrá al menos una solución.

Información sobre el corrector

Podéis escribir las soluciones de este ejercio en cualquier orden.

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
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++