permutation haskell

Question

J'ai une liste:

let a = [1, 2, 3] 

Je dois obtenir une autre liste:

[1, 2, 3] ++ [1*2, 2*3, 1*3] ++ [1*2*3] 

Il est un produit de tous les coombinations possibles uniques des éléments de la liste. J'ai fondé des permutations dans Data.List, mais comme je le vois, c'est quelque chose de différent.

Y at-il des fonctions de bibliothèque pour obtenir cette liste ou pouvez-vous me donner des exemples comment puis-je créer votre propre fonction.

Merci.

Answer 1

Pour une fonction de bibliothèque, vous pouvez utiliser subsequences de Data.List:

Prelude Data.List> subsequences [1,2,3] 
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 

Vous pouvez obtenir tous les produits utilisant map product $ subsequences [1,2,3].

Mais ce n'est pas dans le même ordre que vous avez spécifié. Ainsi, vous pouvez trier, en utilisant sortBy de Data.List et comparing de Data.Ord:

Prelude Data.List Data.Ord> sortBy (comparing length) $ subsequences [1,2,3] 
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 

Encore une fois, obtenir les produits en utilisant map product.

Votre autre idée, pour écrire une fonction vous-même, est la meilleure idée si vous apprenez Haskell. Essaie!

Answer 2

Vous voulez toutes les sous-séquences, pas les permutations. Les permutations vous donnent tous les ordres possibles des mêmes éléments. Alors qu'une sous-séquence est une séquence qui a un sous-ensemble d'éléments de l'original, dans le même ordre.

En plus de la fonction mentionnée ci-dessus, il y a une astuce astucieuse pour faire cela avec d'autres fonctions de la bibliothèque, mais je ne suis pas sûr de savoir à quel point cela vous sera utile.

import Control.Monad (filterM) 

subsequences' :: [a] -> [[a]] 
subsequences' = filterM $ const [False, True] 

Cette astuce profite du point de vue de la liste monade comme la modélisation de calcul non déterministe. Pour chaque élément de la liste, il est inclus ou non, de manière non déterministe, indépendamment de ce que c'est.

C'est efficace, et c'est précisément le genre de chose pour lequel la liste monad est conçue, mais elle est quelque peu opaque. Vous en apprendrez probablement plus en appliquant directement la même idée, en fonction des descriptions que j'ai fournies.