From one to en (2) P53046


Statement
 

pdf   zip

html

Write a program that prints all the permutations of { 1, …, n } with exactly one cycle, for a given n. Assume that the content of the position i of a permutation indicates “the next position to visit”.

For instance, consider the permutation (4,3,2,5,1,7,6). The position 1 has a 4, the position 4 has a 5, and the position 5 has a 1. Therefore, one of the cycles of this permutation is 1 → 4 → 5 → 1. The other two cycles are 2 → 3 → 2 and 6 → 7 → 6. The permutation (3,2,1) has the two cycles 1 → 3 → 1 and 2 → 2. The permutation (3,4,5,6,7,1,2) has only the cycle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Input

Input consists of a natural number n > 0.

Output

Print all the permutations of { 1, …, n } with only one cycle.

Information about the checker

You can print the solutions to this exercise in any order.

Hint

The judge may accept a program that generates all the permutations and, for each one, checks if it only has one cycle. However, this is not the right solution for this problem.

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
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++