Permutations and cycles (1) P93873


Statement
 

pdf   zip

thehtml

Write a program to print all the permutations of {1, …, n} with exactly k cycles, where 1 ≤ kn. For exemple, consider the permutation (4, 3, 2, 5, 1, 7, 6). At position 1 there is a 4, at position 4 there is a 5, and at position 5 there is a 1. Therefore, one of the cycles 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, and the permutation (3,4,5,6,7,1,2) only has the cycle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Input

Input consists of n and k, with 1 ≤ kn.

Output

Print all the permutations of {1, …, n} with k cycles.

Information about the checker

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

Hint

A possible program does not build the permutations consecutively from left to right, but jumping over the solution, using a function

void f(int i, int ini, int cells, int cycles);

where i is the next cell to fill, ini is where the current cycle—still to be closed—starts, cells is the number of cells still free, and cycles is the number of cycles yet to be created.

Public test cases
  • Input

    3 1
    

    Output

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

    3 2
    

    Output

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

    3 3
    

    Output

    (1, 2, 3)
    
  • Information
    Author
    Enric Rodríguez
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++