D'un a ena (2) P53046

Feu un programa que escrigui totes les permutacions de $\{ 1, \dots, n \}$ amb un cicle exactament, per a una $n$ donada. Suposeu que el contingut de la posició $i$ d’una permutació indica “la següent posició que cal visitar”.

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 d’aquesta permutació és $1 \to 4 \to 5 \to 1$. Els altres dos cicles són $2 \to 3 \to 2$ i $6 \to 7 \to 6$. La permutació $(3,2,1)$ té els dos cicles $1 \to 3 \to 1$ i $2 \to 2$, mentre que la permutació $(3,4,5,6,7,1,2)$ només té el cicle $1 \to 3 \to 5 \to 7 \to 2 \to 4 \to 6 \to 1$.

Entrada

L’entrada consisteix en un natural $n > 0$.

Sortida

Escriviu totes les permutacions de $\{ 1, 2, \dots, n \}$ amb un únic cicle.

Informació sobre el corrector

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

Pista

Un programa que generi totes les permutacions i per a cadascuna comprovi si té un únic cicle potser serà acceptat pel jutge, però no és la solució correcta per a aquest problema.