De uno a ene (4) P44612
Haced un programa que escriba las permutaciones de { 1, …, n } con un ciclo exactamente. Suponed que el contenido de la posición i indica “la siguiente posición que hay que visitar”.
Por ejemplo, considerad la permutación (4,3,2,5,1,7,6). En la posición 1 hay un 4, en la posición 4 hay un 5, y en la 5 hay un 1. Así pues, uno de los ciclos de esta permutación es 1 → 4 → 5 → 1 (tiene dos ciclos más). En canvio, la permutación (3,4,5,6,7,1,2) sólo tiene un ciclo: 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.
Para hacer el problema más interesante, algunas posiciones ya estarán fijadas. Usaremos n valores para indicarlo: las posiciones libres tendrán un 0, y las otras el valor ya fijado.
Entrada
La entrada consiste en un natural n > 0 seguido de los n valores para las posiciones fijadas.
Salida
Escribid todas las permutaciones de { 1, …, n } con un único ciclo que tienen las posiciones fijadas dadas. Siempre habrá al menos una solución.
Información sobre el corrector
Podéis escribir las soluciones de este ejercio en cualquier orden.
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
- Spanish
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++