Haskell - Subconjunts P44610


Statement
 

pdf   zip

thehtml

Aquest exercici explora la generació exhaustiva de subconjunts.

  1. Feu una funció zerosNones1 :: Int -> [[Int]] que, donat un n≥0, retorni totes les combinacions de z zeros i u uns tals que z + u = n.
  2. Feu una funció zerosNones2 :: Int -> Int -> [[Int]] que, donats n≥0 i 0≤ un, retorni totes les combinacions de nu zeros i u uns.
  3. Feu una funció subsets1 :: [a] -> [[a]] que, donats n≥0 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≥0 i n≥0 elements, escrigui tots els subconjunts de m elements que es poden formar amb els 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.

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