Combinaisons d'éléments k de jeu N haskell

Question

Je suis en train d'obtenir toutes les combinaisons ordonnées de 3 éléments d'un ensemble de N: éléments, soit: ["A","B","C","D"] ->["ABC","ABD","ACD","BCD"].

Je pensais à écrire quelque chose comme [ x++y++z | pos(x)in list < pos(y) in list < pos(z) in list ]

Comment puis-je faire cela?

Answer 1

Vous pouvez écrire votre fonction pour trois éléments comme l'utilisation tails :: [a] -> [[a]]:

[x++y++z | (x:xs) <- tails list, (y:ys) <- tails xs, (z:_) <- tails ys] 

Cela génère:

Prelude> :m Data.List 
Prelude Data.List> (\list -> [x++y++z | (x:xs) <- tails list, (y:ys) <- tails xs, (z:_) <- tails ys]) ["A","B","C","D"] 
["ABC","ABD","ACD","BCD"] 

Mais généralement, vous voulez une plus solution évolutive (celui où vous pouvez générer des combinaisons de k éléments). Vous pouvez par exemple définir une fonction combinations :: Int -> [a] -> [[a]] comme:

combinations 0 _ = [[]] 
combinations n ls = [ (x:ys) | (x:xs) <- tails ls, ys <- combinations (n-1) xs ] 

et vous devez concat tous les éléments (par exemple en utilisant un map).

Answer 2

Là vous allez:

combinations 0 lst = [[]] 
combinations k lst = do 
    (x:xs) <- tails lst 
    rest <- combinations (n-1) xs 
    return $ x : rest 

Maintenant, pour obtenir le résultat souhaité, utilisez map concat (combinations 3 ["A","B","C","D"]).