Haskell - Subconjunts P44610


Statement
 

pdf   zip

Aquest exercici explora la generació exhaustiva de subconjunts.

  1. Feu una funció zerosNones1 :: Int -> [[Int]] que, donat un n≥0n\ge0, retorni totes les combinacions de zz zeros i uu uns tals que z+u=nz + u = n.

  2. Feu una funció zerosNones2 :: Int -> Int -> [[Int]] que, donats n≥0n\ge0 i 0≤u≤n0\le u\le n, retorni totes les combinacions de n−un-u zeros i uu uns.

  3. Feu una funció subsets1 :: [a] -> [[a]] que, donats n≥0n\ge0 elements, retorni una llista amb tots els subconjunts que es poden formar amb els elements.

  4. Feu una funció subsets2 :: Int -> [a] -> [[a]] que, donats un nombre m≥0m\ge0 i n≥0n\ge0 elements, escrigui tots els subconjunts de mm elements que es poden formar amb els nn 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.

Puntuació

Cada funció puntua 25 punts.

Public test cases

  • Input

    let msort xs = sort (map sort xs)
sort $ zerosNones1 3
sort $ zerosNones2 5 2
msort $ subsets1 ["hola", "adeu", "hi"]
msort $ subsets1 [1..2]
msort $ subsets2 2 ["hola", "adeu", "hi", "hello", "bye"]

    Output

    [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
[[0,0,0,1,1],[0,0,1,0,1],[0,0,1,1,0],[0,1,0,0,1],[0,1,0,1,0],[0,1,1,0,0],[1,0,0,0,1],[1,0,0,1,0],[1,0,1,0,0],[1,1,0,0,0]]
[[],["adeu"],["adeu","hi"],["adeu","hi","hola"],["adeu","hola"],["hi"],["hi","hola"],["hola"]]
[[],[1],[1,2],[2]]
[["adeu","bye"],["adeu","hello"],["adeu","hi"],["adeu","hola"],["bye","hello"],["bye","hi"],["bye","hola"],["hello","hi"],["hello","hola"],["hi","hola"]]
    • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell