D'un a ena (2) P53046


Statement
 

pdf   zip

thehtml

Feu un programa que escrigui totes les permutacions de { 1, …, n } amb un cicle exactament, per a una n donada. Suposeu que el contingut de la posició i d’una permutació 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. Els altres dos cicles són 2 → 3 → 2 i 6 → 7 → 6. La permutació (3,2,1) té els dos cicles 1 → 3 → 1 i 2 → 2, mentre que la permutació (3,4,5,6,7,1,2) només té el cicle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Entrada

L’entrada consisteix en un natural n > 0.

Sortida

Escriviu totes les permutacions de { 1, 2, …, n } amb un únic cicle.

Informació sobre el corrector

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

Pista

Un programa que generi totes les permutacions i per a cadascuna comprovi si té un únic cicle potser serà acceptat pel jutge, però no és la solució correcta per a aquest problema.

Public test cases
  • Input

    3
    

    Output

    (2,3,1)
    (3,1,2)
    
  • Input

    4
    

    Output

    (2,3,4,1)
    (2,4,1,3)
    (3,4,2,1)
    (3,1,4,2)
    (4,3,1,2)
    (4,1,2,3)
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python