Afficher tous les sous-ensembles de 1 a N

Afficher tous les sous-ensembles de 1 a N - Algo - Programmation

Marsh Posté le 14-10-2006 à 17:45:55    

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


Message édité par pinpoy le 14-10-2006 à 17:46:39
Reply

Marsh Posté le 14-10-2006 à 17:45:55   

Reply

Marsh Posté le 14-10-2006 à 17:56:23    

fait du récursif.


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 14-10-2006 à 19:29:20    

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

Reply

Marsh Posté le 14-10-2006 à 22:55:04    

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.


Message édité par Trap D le 14-10-2006 à 23:45:44
Reply

Marsh Posté le 14-10-2006 à 23:37:53    

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

Reply

Marsh Posté le 14-10-2006 à 23:47:12    

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.


Message édité par 0x90 le 14-10-2006 à 23:47:45

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 15-10-2006 à 00:33:48    

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

Reply

Marsh Posté le 15-10-2006 à 00:41:32    

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


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 15-10-2006 à 01:10:57    

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

Reply

Marsh Posté le 15-10-2006 à 01:20:01    

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 ;) )


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 15-10-2006 à 01:20:01   

Reply

Marsh Posté le 15-10-2006 à 15:19:56    

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

Reply

Marsh Posté le 17-10-2006 à 22:14:09    

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

Code :
  1. /**
  2.  * -return all nCp subsets (with nCp = n!/(p!(n-p)!))
  3.  * -The algorithm uses a depth-first search technic with limited depth
  4.  * the limit is p value.
  5.  * -At final, each data in the LinkedList contains a subset
  6.  */
  7. protected LinkedList generateAllSubSets (int n, int p)
  8. {
  9.  Node root, node;
  10.  LinkedList subSets;
  11.  int[] subSet;
  12.  int i;
  13.  Stack stack;
  14.  root = new Node (0, 0, null);
  15.  subSets = new LinkedList ();
  16.  stack = new Stack ();
  17.  stack.push (root);
  18.  //depth-first search algorithm
  19.  while (!stack.empty ())
  20.  {
  21.   node = (Node) stack.pop ();
  22.   //the limited depth has been reached
  23.   if (node.depth == p)
  24.   {
  25.    //construct the new subset
  26.    subSet = new int[p];
  27.    i = p-1;
  28.    while (node.parent != null)
  29.    {
  30.     subSet[i--] = node.value-1;
  31.     node = node.parent;
  32.    }
  33.    //add the subset
  34.    subSets.addFirst (subSet);
  35.   }
  36.   //we continue to explore the tree
  37.   else if (node.depth < p)
  38.    for (i = node.value + 1; i <= n; i++)
  39.     stack.push (new Node (i, node.depth + 1, node));
  40.  }
  41.  return subSets;
  42. }


 
et la classe Node associée :
 

Code :
  1. /**
  2. * Define a subSet of population contructs from the reference set
  3. */
  4. class Node
  5. {
  6. public int value;
  7. public int depth;
  8. public Node parent;
  9. public Node (int value, int depth, Node parent)
  10. {
  11.  this.value = value;
  12.  this.depth = depth;
  13.  this.parent = parent;
  14. }
  15. }


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


Message édité par Giz le 17-10-2006 à 22:17:37

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
Reply

Marsh Posté le 18-10-2006 à 12:47:02    

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

Spoiler :

int sous_ensembles(int N, int n, int tab[])
{
 int  i=0;
 int  nb_elements=0;
 int  debut=0;
 
 if (N < 1) {fprintf(stderr, "sous_ensembles : paramètre \"N\" non valide.\n" );return ERREUR;}
 if (n < 0) {fprintf(stderr, "sous_ensembles : paramètre \"n\" non valide.\n" );return ERREUR;}
 
 /* Un sous-ensemble a été trouvé ! */
 if (n >= N)
  {
   Affichage; décompte, ...
   return OK;
  }
 
 /* Recherche */
 debut=0;
 if ( (n > 0) && (tab[n-1] > 0) ) debut=tab[n-1]+1;
 for (i=debut;i<=N;i++)
  {
   tab[n]=i;
   ensembles(N, n+1, tab);
  }
 
 /* Fin */
 return OK;
}


 
Avec l'appel de la fonction récursive :

Spoiler :

ensembles(N, 0, tab);


---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 18-10-2006 à 14:48:41    

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


---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
Reply

Marsh Posté le 18-10-2006 à 15:18:14    

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

Code :
  1. void sets(size_t n)
  2. {
  3.     size_t i=0,j;
  4.     char *t = calloc(sizeof(*t), n);
  5.     while (i!=n) {
  6.         for (i=0; i<n; i++) {
  7.             if (t[i]==1) {
  8.                 t[i]=0;
  9.             } else {
  10.                 t[i]=1;
  11.                 break;
  12.             }
  13.         }
  14.         for (j=0; j<n; j++) {
  15.             if (t[j]) {
  16.                 printf("%i ", j+1);
  17.             }
  18.         }
  19.         putchar('\n');
  20.     }
  21.     free(t);
  22. }


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 20-10-2006 à 12:01:01    

Code :
  1. #include <iostream.h>
  2. #include <math.h>
  3. //decomposition d'un entier n en base 2 dans un tableau de taille m
  4. void decomp(int n, int m){
  5. bool virg=0; //pour avoir un affichage correct
  6. int t[m];
  7. int last;
  8. for (int i=0; i<m; i++){//T contiendra n coder en binaire
  9.  t[i] = n % 2;
  10.  n /= 2;
  11. }
  12. for (int i=0; i<m; i++){
  13.  if(t[i]==1){
  14.   if(virg==0){
  15.    cout<<i+1;
  16.    virg=true;
  17.    }
  18.    else
  19.    {
  20.    cout<<","<<i+1;
  21.    }
  22.  }
  23. }
  24. }
  25. int main(){
  26. cout<<"Valeur de n:";
  27. int m;
  28. cin>>m;
  29. for (int j=0; j<pow(2,m); j++){ //pour un entier m => affichage des (2^m) -1       //1ers entiers en base2
  30.  cout<<"{";
  31.  decomp(j,m);
  32.  //ci dessous juste pour avoir un affichage correct
  33.  if(j<pow(2,m)-1){
  34.   cout<<"} ,";
  35.   }
  36.   else
  37.   {
  38.   cout<<"} ";
  39.   }
  40. }
  41. return 0;
  42. }


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


Message édité par pinpoy le 20-10-2006 à 12:17:34
Reply

Marsh Posté le 20-10-2006 à 14:22:34    

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


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 21-10-2006 à 13:22:56    

jai lu mais jai pas compris :p

Reply

Marsh Posté le 22-10-2006 à 01:31:34    

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 :
 


let rec parties = function
| 0 -> [[]]
| n -> let ps = parties (n-1) in ps @ (List.map (fun p -> n::p) ps)


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

Reply

Marsh Posté le 22-10-2006 à 17:44:35    

Voici une version récursive terminale* :
 

let parties =
  let rec parties res = function  
  | 0 -> res
  | n ->  
      parties (res @ List.map (fun p -> n::p) res) (n-1)
  in parties [[]]


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


Message édité par pwang le 22-10-2006 à 17:48:05

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.
Reply

Marsh Posté le 22-10-2006 à 19:49:37    

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... :heink:

Reply

Marsh Posté le 22-10-2006 à 19:58:30    

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

Reply

Marsh Posté le 22-10-2006 à 20:06:30    

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

let parties =
  let rec parties res = function  
    | 0 -> res
    | n ->
      parties
           (List.rev_append
                res
                (List.rev_map (fun p -> n::p) res))
           (n-1)
  in parties [[]]


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


Message édité par pwang le 22-10-2006 à 20:08:51

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.
Reply

Marsh Posté le 22-10-2006 à 20:08:11    

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

Message cité 1 fois
Message édité par nyrk le 22-10-2006 à 20:08:52
Reply

Marsh Posté le 22-10-2006 à 20:09:33    

nyrk a écrit :


Edit: grillé pour la version complètement récursive terminale. :D


:P


Message édité par pwang le 22-10-2006 à 20:09:51

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed