Permutacions i cicles (1) P93873

Statement

thehtml

Feu un programa que escrigui totes les permutacions de {1, …, n} amb exactament k cicles, on 1 ≤ k ≤ n. 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 é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 n i k, amb 1 ≤ k ≤ n.

Sortida

Escriviu totes les permutacions de {1, …, n} amb k cicles.

Informació sobre el corrector

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

Pista

Un programa possible no crea les permutacions consecutivament d’esquerra a dreta, sinó saltant pel vector solució, usant una funció

void f(int i, int ini, int caselles, int cicles);

on i és la següent posició a omplir, ini és on comença el cicle actual encara no tancat, caselles és el nombre de caselles encara lliures, i cicles és el nombre de cicles que encara falta crear.

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++