Compréhension de liste: faire des listes de listes

Question

Salut im essayant de faire une fonction dans haskell qui prend un nombre a fait une partie de celui-ci utilisant des listes c'est-à-dire pour le numéro 4 il créerait [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]. J'envisageais d'utiliser la compréhension de la liste pour créer une liste x puis créer d'autres listes en utilisant les nombres de [1 ... n] (n étant le numéro de partition que je voudrais) où la somme de la liste créée serait égale tonne.

Le code que j'ai créé jusqu'à présent est-

partions (n:xs) = [[x|x<-[1...n], sum[x]==n]]|xs<-[1..]] 

mais obiviously cela ne fonctionne pas, des suggestions?

merci.

Answer 1

Je suggère d'essayer la récursivité: Pour obtenir les partitions de n, parcourir les nombres i = 1 à n, et générer récursivement les partitions de (ni), le cas de base étant que la seule partition de 1 est 1 et la partition de 0 est la liste vide.

Answer 2

Je suis un peu rouillé avec Haskell, mais peut-être que le code suivant peut vous guider pour trouver la solution.

parts :: Int -> Int -> [[Int]] 
parts 0 p = [[]] 
parts x p = [(y:ys) | y <-[p..x], ys <- (parts (x - y) y)] 

Et vous devez appeler pièces avec x = n, et p = 1.

EDIT

J'ai fixé le cas de base lorsque x est égal à 0 pour retourner un liste avec un seul élément, étant cet élément une liste vide. Maintenant, il fonctionne très bien :)

Answer 3

Que diriez-vous ... ce

import Data.List (nub, sort) 

parts :: Int -> [[Int]] 
parts 0 = [] 
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)] 

L'essayer:

*Main Control.Monad> forM [1..5] (print . parts) 
[[1]] 
[[2],[1,1]] 
[[3],[1,2],[1,1,1]] 
[[4],[1,3],[1,1,2],[1,1,1,1],[2,2]] 
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[2,3]] 

Je pense qu'il est correct, sinon efficace.

Answer 4

J'ai trouvé utile de définir une fonction auxiliaire, partitionsCap, qui ne laisse aucun des éléments dépasser une valeur donnée. Utilisé récursive, il peut être utilisé pour produire uniquement les monotonically résultats décroissants que vous voulez (pas de [1,3,1] lorsque vous avez déjà [1,1,3]):

partitions :: Int -> [[Int]] 
partitions n = partitionsCap n n 

partitionsCap :: Int -> Int -> [[Int]] 
partitionsCap cap n 
    | n < 0 = error "partitions: negative number" 
    | n == 0 = [[]] 
    | n > 0 = [i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
       where hi = min cap n 

---

Au cœur de l'algorithme est l'idée que, lors du partitionnement N, vous prenez i de n jusqu'à 1, et préfixez i aux partitions de n-i. Simplifié:

concat [map (i:) $ partitions (n-i) | i <- [n,n-1..1]] 

mais mal:

> partitions 3 
[[3],[2,1],[1,2],[1,1,1]] 

Nous voulons que [1,2] aller loin.Par conséquent, nous avons besoin de plafonner les partitions que nous sommes à préfixer donc ils ne vont pas au-dessus i:

concat [map (i:) $ partitionsCap i (n-i) | i <- [hi,hi-1..1]] 
where hi = min cap n 

Maintenant, pour le nettoyer: que concat et carte si proches attiré mon attention . Un peu d'arrière-plan: les listes de compréhension et la liste monad sont very closely related, et concatMap est le même que >>= avec ses arguments retournés, dans la liste monad. Donc, je me demandais: est-ce que ces concat et carte se transforment en quelque sorte en >>=, et peut-il que >>= en quelque sorte douce-parler son chemin dans la compréhension de la liste?

Dans ce cas, la réponse est oui :-)

[i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
where hi = min cap n