D'un a ena (4) P44612
Feu un programa que escrigui totes les permutacions de { 1, …, n } amb un cicle exactament. Suposeu que el contingut de la posició i 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 → 4 → 5 → 1 (té dos cicles més). En canvi, la permutació (3,4,5,6,7,1,2) només té un cicle: 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.
Per fer aquest problema més interessant, algunes de les posicions ja estaran fixades. Usarem n valors per indicar-ho: les posicions lliures tindran un 0, i les altres el valor ja fixat.
Entrada
L’entrada consisteix en un natural n > 0 seguit dels n valors per indicar les posicions fixades.
Sortida
Escriviu totes les permutacions de { 1, 2, …, n } amb un únic cicle que tenen les posicions fixades donades. Sempre hi haurà almenys una solució.
Informació sobre el corrector
Podeu escriure les solucions d’aquest exercici en qualsevol ordre.
Input
1 0
Output
(1)
Input
3 0 0 0
Output
(2,3,1) (3,1,2)
Input
6 4 0 6 0 0 0
Output
(4,3,6,2,1,5) (4,5,6,2,3,1) (4,5,6,3,1,2) (4,1,6,3,2,5) (4,3,6,5,2,1) (4,1,6,5,3,2)
Input
7 3 4 0 6 0 1 2
Output
(3,4,5,6,7,1,2)
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++