# Permutations and cycles (1) P93873

Statement html

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.

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