Bonjour,jai un tit probleme dalgorithmique à résoudre qui consiste a afficher tous les sous ensemble dentiers de 1 a N....
 
par exemble si je choisis N=3 ca donne
 
{}, {1}, {2} ,{3}, {1, 2}, {2, 3}, {1,3}, {1, 2 ,3}
 
 
il faut bien sur que ca marche pour nimporte quel entier posistif....et jai beau réfléchir je ne vois pas comment faire...
 
donc si vous avez une idée qui pourrait marcher ou un indice sur la facon de procéder ou meme la solution... je suis preneur ^^
 
 
merci davance

fait du récursif.

commence déjà par calculer combien il existe d'ensemble distincts pour N

Celà se fait plutôt avec une file.
Il y aussi une possibilité amusante avec le nombre de sous ensembles possibles écrit en base 2.

y a pas de récursion, il suffit d'énumérer en comptant en Base N de 0 à N**N

Bha tu peut considérer que tout les sous ensembles pour N=x sont tout les sous ensembles pour N=x-1 union ces même ensembles auquel tu a ajouté x.
 
Et, heu, si je compte en base N de 0 à N**N je tombe pour n = 3 sur:
0
1
2
10
11
12
t'interprète comment 11 ?
 
j'aurais plutot pensé énumerer les représentations binaires des entiers de 0 à 2^N pour faire dans l'itératif.

J'interprète pas 11 parce que c'est n'est pas un ensemble.
 
c'est pas la peine de passer en binaire ...

Y'a des fois t'es tellement clair qu'on croirait que tu nous parle d'à travers ton cul

avec N =  3
 
1 -> ,,1
2 -> ,,2
3 -> ,,3
11 -> doublon, pas un ensemble
12 -> ,1,2
13 -> ,1,3
21 -> on a déjà
22 -> doublon, pas un ensemble
23 -> ,2,3
31 -> on a déjà
32 -> on a déjà
33 -> pas un ensemble
111-> pas un ensemble
etc ...
 
y a sans doute des tas de méthodes pour faire ces différentes combinaisons, plus ou moins efficace, mais c'est pas sorcier. Il y a "somme( pour k de 1 à n: C(k, n))" ensembles, si je ne me vautre pas. Pour n = 3, ça fait 3 + 3 + 1 = 7

Ok, ca fait quand même beaucoup de doublons / on a déja à éliminer
 
Et pour le nombre de solutions, tu prends chaque élément, tu leur assigne à chacun un bit d'un nombre binaire qui signifie ou non leur présence dans l'ensemble, et tu énumère les nombres binaires de longueur n,  y'en a 2^n.
 
( mais passer par une représentation binaire qu'on incrémente puis ou on teste tout les bits est pas forcément efficace, par contre un algo genre code de gray directement sur l'ensemble est très envisageable )

merci bcp a taz ....................(et aux autres aussi   )
 
je vais coder ca et je vous tiendrais au courant sur la maniere voulu par le prof au cas ou ca vs intéresse  

Tiens, un bout de code qui trainait sur mon dur, il devrait répondre à tes besoins :

 
et la classe Node associée :
 

 
Bon tu es sur la bonne piste avec ça...(suffit de faire des appels avec des valeurs différentes de p)

J'avais fais un truc similaire en C il y a pas mal de temps. J'avais utilisé une fonction récursive.

 
Avec l'appel de la fonction récursive :

En Java, perso, sans limite de perf, et sans vouloir me faire chier, je coderais une classe ensemble avec des methodes Add/Remove/CompareTo/Contains.
 
Je genererais tout les ensembles possibles avec des boucles, en les metant dans un Vecteur d'ensemble. Et apres je filtrerais les mauvais grace au methodes ecritent avant.
 
Rapide a code je pense, pas besoin d'etre un fou en maths... Mais sans doute tres lent

Bon ben puisque c'est la fête aux algos :

void sets(size_t n)
{
    size_t i=0,j;
    char *t = calloc(sizeof(*t), n);
    while (i!=n) {
        for (i=0; i<n; i++) {
            if (t[i]==1) {
                t[i]=0;
            } else {
                t[i]=1;
                break;
            }
        }
        for (j=0; j<n; j++) {
            if (t[j]) {
                printf("%i ", j+1);
            }
        }
        putchar('\n');
    }
    free(t);
}

 
 
le principe est le suivant :  
on va stocker chaque nombre entre 0 et N en binaire dans un tableau int t[m];
 
par exemple pour N=3, on obtiendra les tableaux suivants
 
000     pour 0
001     pour 1
010     pour 2
011     pour 3
100     pour 4
101     pour 5
110     pour 6
111     pour 7
 
on a donc toutes les possibilité d'ensemble a 3 éléments si l'on considere l'indice de chaque élément + 1
 
000  --> {}
001  --> {3}
010  --> {2}
011  --> {2, 3}
100  --> {1}
101  --> {1, 3}
110  --> {1, 2}
111  --> {1, 2, 3}
 
 
cest sur fallait y penser  

Ca serait bien de lire des fois, c'est exactement ce que j'ai dit et fait, en plus efficace...

jai lu mais jai pas compris

Pour répondre à la question de départ, n'ayant pas vraiment vu de description simple de l'algorithme :
 
Il y a deux sortes de parties de l'ensemble {1, 2, ..., N}, celles qui contiennent N et celles qui ne le contiennent pas. Lister l'ensemble des parties qui ne contiennent pas N revient à résoudre le problème pour N-1 et donc pour résoudre le problème pour N, il suffit de lister en plus les parties qui contiennent N qui sont tout simplement les parties de {1, ..., N-1} auxquelles on a ajouté N. Une implémentation en Caml pourrait être :
 

 
Élégante mais cependant non récursive terminale donc seulement valable pour un devoir (:D) ou si les performances ne sont pas importante.

Voici une version récursive terminale* :
 

 
 
 
* c'est-à-dire que les appels récursifs n'ont pas besoin d'adresse de retour, et que le compilateur sait dérouler ce genre de fonctions pour les rendre de même efficacité que l'écriture impérative avec des boucles for ou while. Attention : le compilateur n'est pas capable de détecter tous les cas de recursion dont on souhaiterait qu'elle soit terminale... mais la plupart du temps c'est fait ! Et bien sûr, l'intérêt de la récursion est la concision...

Ta version est bien récursive terminale mais étrangement elle plante chez moi pour n >= 16 avec l'exception "Stack overflow during evaluation (looping recursion?).". J'ai essayé de remplacer la fonction "@" par "List.rev_append" qui est récursive terminale, mais ça ne change rien. Je ne vois pas où est le problème...

List.map n'est pas récursive terminale...
 
Et... étant donné que la liste finale est de longueur 2^16... euh... ça fait peut-être beaucoup sur la pile...
 

Voici une version totalement récursive terminale (enfin j'espère ) :
 

 
(en tout cas il fait passer parties 17 - et même 18... - alors que sinon à 16 il refuse)

Je suis bête d'avoir pensé à @ mais pas à List.map.
 
Edit: grillé pour la version complètement récursive terminale.