énumération à partir d'un ensemble

**marc2009** · 22/08/2007, 15h36

Bonjour,
voici mon problème à moi :
Je veux faire de l'énumération à partir d'un ensemble A={1, 2,3,4,5}
et le résultat que je veux est du style :{1},{2},{3},{4},{5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4} etc...(au total 2^n)
avez vous une heuristique d'énumerer tous les cas possibles (2^n) ?

Merci d'avance.

**Nemerle** · 22/08/2007, 16h02

fais une recherche dans ce forum, on a du répondre à ce type de question à peu près 1000000 fois...

**marc2009** · 22/08/2007, 16h10

beh, je ne trouve rien sur ce forum. merci

**Jedai** · 22/08/2007, 16h47

Cherche mieux !
Powerset (c'est le nom anglais de ce que tu cherches, en français on dit simplement "parties d'un ensemble") en Haskell :

Code :

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

powerset = filterM $ const [True, False]

ou, moins cryptique (quoique) :

Code :

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

1
2
3
4
5
6
7
8
powerset       :: [a] -> [[a]]
powerset []     = [[]]
powerset (x:xs) = xss /\/ map (x:) xss
  where xss = powerset xs
 
(/\/)        :: [a] -> [a] -> [a]
[] /\/ ys = ys
(x:xs) /\/ ys = x : (ys /\/ xs)

Remarque : cette seconde version permet de parcourir l'ensemble des possibilités en mémoire constante.

--
Jedaï

**marc2009** · 22/08/2007, 16h57

je trouve ta réponse pertinente Jedai. Merci.
Mais est ce que tu peux etre plus claire dans ton code?
ou alors possède tu un pseudo code?

Merci

**Jedai** · 22/08/2007, 17h02

Envoyé par marc2009

je trouve ta réponse pertinente Jedai. Merci.
Mais est ce que tu peux etre plus claire dans ton code?
ou alors possède tu un pseudo code?

Merci

Quel langage utilises-tu ? S'il s'agit d'un langage impératif, cet algorithme ne te sera peut-être pas d'un grand secours, il s'appuie sur la nature non-stricte et fonctionnelle d'Haskell pour offrir une solution efficace.

Cherche plutôt "parties d'un ensemble" sur le forum ou sur Google. Au jour d'aujourd'hui une compétence indispensable à un programmeur c'est la capacité à rechercher un algorithme sur Internet.

--
Jedaï

**pseudocode** · 22/08/2007, 16h58

Envoyé par Jedai

ou, moins cryptique (quoique)

avez vous une heuristique d'énumerer tous les cas possibles (2^n)

Hum... si tu sais deja qu'il y en a 2^n, l'heuristique est pas trop dure a trouver. Surtout si tu sais ecrire en binaire les nombres de 1 a 2^n....

**marc2009** · 22/08/2007, 17h04

et alors , t'as une ptite idée?

**Jedai** · 22/08/2007, 17h17

Envoyé par pseudocode

ou, moins cryptique (quoique)

Non pas vraiment, c'est juste de la récursion simple (avec une petite astuce pour la mémoire constante), oublions temporairement /\/ et remplaçons le par ++, l'opérateur classique de concaténation de liste.

Code :

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

1
2
3
4
powerset       :: [a] -> [[a]]
powerset []     = [[]]
powerset (x:xs) = xss ++ map (x:) xss
  where xss = powerset xs

Cas de base : powerset de l'ensemble vide est l'ensemble contenant l'ensemble vide.
Récursion sur une liste de tête x et de queue xs : il y a les parties qui ne contiennent pas x (powerset xs) et les parties qui contiennent x (tous les éléments de (powerset xs) à qui on ajoute x).
Vérification de la récursion : chaque appel récursif se fait avec une liste de longueur strictement inférieure à la liste initiale, le cas de base nous assure que la récursion s'arrêtera.

L'opérateur /\/ qu'on définit ensuite permet d'alterner entre élément de son premier argument et élément de son second argument, par exemple :

Code :

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