Permutacions i cicles (1) P93873

Feu un programa que escrigui totes les permutacions de $\{1, \ldots, n\}$ amb exactament $k$ cicles, on $1 \le k \le 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 \rightarrow 4 \rightarrow 5 \rightarrow 1$. Els altres dos cicles són $2 \rightarrow 3 \rightarrow 2$ i $6 \rightarrow 7 \rightarrow 6$. La permutació $(3,2,1)$ té els dos cicles $1 \rightarrow 3 \rightarrow 1$ i $2 \rightarrow 2$, mentre que la permutació $(3,4,5,6,7,1,2)$ només té el cicle $1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 1$.

Entrada

L’entrada consisteix en $n$ i $k$, amb $1 \le k \le n$.

Sortida

Escriviu totes les permutacions de $\{1, \ldots, 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.