é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

**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....

**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ï

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

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

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

j'utilise le C++ Builder.

**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

[1,2,3] /\/ [4, 5] == [1,4,2,5,3]

L'évaluation paresseuse fait le reste, et cette solution s'exécute en mémoire constante.

--
Jedaï

**pseudocode** · 22/08/2007, 17h21

Envoyé par marc2009

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

Code :

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

1
2
3
4
5
6
7
8
9
10
E={a,b,c,d,e}
 
 0 = 00000 --> {}
 1 = 00001 --> {e}
 2 = 00010 --> {d}
 3 = 00011 --> {d,e}
 4 = 00100 --> {c}
..
30 = 11110 = {a,b,c,d}
31 = 11111 = {a,b,c,d,e}

c'est une idée...

@Jedai: Plus ca va, plus je trouve le code Haskell "élégant"... ca commence a m'inquieter

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

Envoyé par marc2009

j'utilise le C++ Builder.

Dans ce cas, Pseudocode t'as donné une très bonne idée, énumérer les nombres de 0 à (2^n - 1), et trouver une opération prenant un de ces nombres et le tableau initial et retournant la partie correspondante.

--
Jedaï

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

Ok, ça a l'aire d'une bonne idée. merci.
il me reste juste alors à coder chaque nombre en binaire.
Merci.

**pseudocode** · 22/08/2007, 17h39

Envoyé par marc2009

Ok, ça a l'aire d'une bonne idée. merci.
il me reste juste alors à coder chaque nombre en binaire.
Merci.

. Y a de grande chance que C++Builder gere deja les int/long en binaire...

Il te reste juste a savoir si un bit est a 0 ou a 1... Je te suggere de regarder l'operateur & (AND binaire) et l'operateur >> (decalage de bit a droite).

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

Juste une question :
est ce que le codage de 2^n chiffres en binaires va se faire en un temps polynomial ? car si ce n'est pas le cas, on passe un temps fou dans la conversion en code binaire, et on ne gagne pas grand chose.!!!
sinon, c'est gagné.

**pseudocode** · 22/08/2007, 17h50

Envoyé par marc2009

Juste une question :
est ce que le codage de 2^n chiffres en binaires va se faire en un temps polynomial ? car si ce n'est pas le cas, on passe un temps fou dans la conversion en code binaire, et on ne gagne pas grand chose.!!!
sinon, c'est gagné.

Les "INT" et les "LONG" en C++ *SONT* des chiffres binaires !!!!! Il n'y a pas besoin de les convertir en binaire, il y sont deja.

C'est lorsque tu veux les afficher/gerer en decimal qu'il y a une conversion.

**marc2009** · 22/08/2007, 18h14

Je tiens à vous remercier de vos réponses si pertinentes.
A bientôt sur le forum.

alex_pi · 25/08/2007, 21h49

Envoyé par marc2009

Juste une question :
est ce que le codage de 2^n chiffres en binaires va se faire en un temps polynomial ?

Quand on parle de "temps polynomial", il est parfois bon de dire en quoi on espère être polynomial...
Si c'est en "n", la réponse est bien évidement "non" ! Aucun algorithme classique, sur nombre fini de processeur, n'est capable de produire un nombre exponentiel de sortie en un temps polynomial, c'est assez évident...

Si c'est polynomial en 2^n, bien sûr, c'est même linéaire. Il suffit de faire un for i = 0 to 1 << n do blahblah done. (après, je ne suis pas très au fait des optimisations dans ce genre de cas, et je pense même que c'est compilo et OS dépendant, , donc il faut peut être mieux définir deuxPn= 1 << n avant, et l'utiliser dans la condition de boucle)