énumération à partir d'un ensemble

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.

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

beh, je ne trouve rien sur ce forum. merci

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:

---

powerset = filterM $ const [True, False]

---

ou, moins cryptique (quoique) :

Code:

---

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ï

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

Citation:

---

Envoyé par Jedai

ou, moins cryptique (quoique)

---

:hola:

Citation:

---

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.... :roll: ;)

Citation:

---

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ï

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

j'utilise le C++ Builder.

Citation:

---

Envoyé par pseudocode

Citation:

---

ou, moins cryptique (quoique)

---

:hola:

---

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:

---

1 2 3 4

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

---

1. Cas de base : powerset de l'ensemble vide est l'ensemble contenant l'ensemble vide.
2. 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).
3. 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:

---

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

Citation:

---

Envoyé par marc2009

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

---

Code:

---

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 :mrgreen:

Citation:

---

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ï

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

Citation:

---

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.

---

:mouarf:. 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). ;)

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

Citation:

---

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.

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

Citation:

---

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)

Citation:

---

Si c'est polynomial en 2^n,

---

Depuis quand une fonction en O(2^n) est polynomiale ? 8O

Citation:

---

Envoyé par PRomu@ld

Depuis quand une fonction en O(2^n) est polynomiale ? 8O

---

Il veut dire que coder 2^n chiffres est linéaire en 2^n.

--
Jedaï