Haskell - Permutacions unicícliques P22439


Statement
 

pdf   zip

thehtml

Feu una funció unicycles :: Int -> [[Int]] que, donat un nombre n>0, retorni totes les permutacions de [1..n] amb un cicle exactament. 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 → 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.

Pista

Hi ha (n−1)! permutacions unicícliques de n elements.

Observació

Per tal que no importi l’ordre en que genereu la solució, els jocs de proves ordenen el resultat. Per a això, importeu la funció sort del mòdul Data.List encara que no la feu servir.

Public test cases
  • Input

    sort $ unicycles 3
    sort $ unicycles 4
    

    Output

    [[2,3,1],[3,1,2]]
    [[2,3,4,1],[2,4,1,3],[3,1,4,2],[3,4,2,1],[4,1,2,3],[4,3,1,2]]
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell