afficher les sous ensembles d un ensembles. (gray inside)

afficher les sous ensembles d un ensembles. (gray inside) - Algo - Programmation

Marsh Posté le 10-04-2004 à 06:36:21    

:hello: ,
exemple :
l ensemble {1 2 3 }
donnera
 

{1 2 3}
{1 2}
{1 3}
{1}
{2 3}
{2}
{3}
{}

j ai trouve des expliquation fesant reference au "Binary Reflected Gray Code"
http://www.theory.csc.uvic.ca/~cos [...] tInfo.html
 
mais je ne comprend pas comment passe de {1 2 3} a 111, 3 a pour binaire 011 et le gray code donnera donc 100.
 
ils prennet la chaine a l envers : 321
chaque code de triplet possible correspond on c a une solution du problem (2^n solution), chaque chiffre du code indiquant le chiffre de lemsemble a afficher :
 
exemple :
sur leur site { 1 2 }  ->    0 1 1    
en superposant l ensemble    3 2 1
de droite a gauche on obtient bien { 1 2 }
 
bref..
comment font il pour pour passer d en ensemble au code triplet et comment pouraije afficher les sous esembles dans l ordre montre plus haut ?     [:dams86]  
merci  :)

Reply

Marsh Posté le 10-04-2004 à 06:36:21   

Reply

Marsh Posté le 10-04-2004 à 10:44:56    

:/ aucune idee ?

Reply

Marsh Posté le 10-04-2004 à 19:44:51    

bah à chaque élément de l'ensemble, tu associes un bit de présence : 1 si l'élément est dans le sous-ensemble, 0 sinon. Donc l'ensemble {1 2 3 4 } vaut 1111 et {} vaut 0000. Maintenant pour énumérer tous les sous-ensembles, il te faut un algo qui permette d'énumérer les 2^4 combinaisons entre 1111 et 0000. Y'a des algo pour ça, par exemple l'algo de broadcast dans un hypercube en partant de l'ensemble complet

Reply

Marsh Posté le 11-04-2004 à 04:50:44    

Code :
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. void appendBitCode(int n, int* table, int max, vector<string>& stock) {
  7.   int i;
  8.   string temp="";
  9.   const double y = 10;
  10.  
  11.   //bitstring (graycode)
  12.   for (i=1; i<=max ;++i){
  13.        temp+= char(table[i])+48;
  14.   }
  15.   stock.push_back(temp);
  16. }
  17. void flip(int n, int* table, int max,  vector<string>& stock) {
  18.   appendBitCode(n, table, max, stock);
  19.   //flip point
  20.   table[n] = 1 - table[n];
  21. }
  22. //Binary Reflected Gray Code
  23. void BRGC (int n, int* table, int max, vector<string>& stock) {
  24.   if (n > 0) {
  25.      BRGC(n-1, table, max, stock);
  26.      flip(n, table, max, stock);
  27.      BRGC(n-1, table, max, stock);
  28.   }
  29. }
  30. int main() {
  31.     while (true) {
  32.         vector<string> stock;
  33.         int n; cin >> n;
  34.         int* table = new int[n];
  35.         //initialise the array to 0
  36.         for (int i=1; i<=n ;++i) table[i] = 0;
  37.         BRGC(n, table, n, stock);
  38.         appendBitCode(n, table, n, stock);
  39.         sort ( stock.rbegin (),  stock.rend ());
  40.         for (int i=0; i< stock.size(); i++) {
  41.         cout << "{ ";
  42.                 for (int j=0; j < n; j++) {
  43.                 if (stock[i][j]=='1') cout << j+1 << " ";
  44.               }
  45.         cout << "}";
  46.         cout << endl;
  47.     }
  48.     delete table;
  49.     stock.clear();
  50.     }
  51.     return 0;
  52. }


 
je me suis inspire de morceau de code existant, mais pout suivre lordre  
demande j utilise un vecteur qui contient les diffrentes possibilite pour n (0000 0001 ect.), avec un sort et c est bon :)

Reply

Marsh Posté le 12-04-2004 à 16:59:05    

Ouaip, à vue de nez, ça doit marcher. Vu que tu pars de {}, dans la routine flip tu peux te contenter de faire table[n]=1. Pour le tri, c'est l'ordre lexicographique, un bête tri sur la taille des chaînes suffit.

Reply

Marsh Posté le 12-04-2004 à 17:04:31    

sinon une autre idée : à chaque nombre entre 0 et 2^n (n est la taille de ton ensemble) correspond un sous-ensemble. Pour ça, tu utilises la représentation binaire de ce nombre. Donc tu stockes tous les nombres entre 0 et 2^n et tu les tries selon le nombre de 1 qu'ils contiennent dans leur représentation binaire....

Reply

Sujets relatifs:

Leave a Replay

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