Discussion :

[alex_pi]

Sur le forum algorithmique (http://www.developpez.net/forums/d59...aison-tableau/), un gentil PO demande comment récupérer les sous ensemble d'un ensemble trié. Réponse de Jedai :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
{- Le code demandé calcule en fait les parties d'un ensemble 
modélisé comme une liste ordonnée .
Le nom anglais pour Parties() est powerset, nous l'utiliserons ici -}
 
-- powerset prend une liste d'élément et renvoie une liste de listes
powerset :: [a] -> [[a]]
-- la seule partie de l'ensemble vide est l'ensemble vide
powerset [] = [[]]
-- P( {x1} u {x2, x3, .. xn } ) = (U_{p in P( { x2, .. xn } ) {x1} u p) u P( { x2, .. xn } ) 
powerset (x:xs) = map (x:) psXs ++ psXs
  where psXs = powerset xs

On peut faire un peu plus rapide et moins gourmant en mémoire avec :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
powerset [] = [[]]
powerset (x:xs) = interleave (map (x:) psXs) psXs
  where psXs = powerset xs
 
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

Je n'arrive pas à voir en quoi la seconde solution est plus efficace. D'un point de vue de Cameleux, elle me parrait moins efficace puisqu'on parcourt les deux liste completement au lieu de partager la seconde. J'imagine que ça doit venir de la paresse, mais je n'arrive pas à mettre le doigt sur un argument valable.