Potenzmenge bilden

Hi,

kennt jemand einen Algorithmus zur bildung der Potenzmenge? So dass man das ganze auch in einer Programmiersprache wie C++ umsetzen kann. Scheint mir nach dem ersten drueber nachdenken keinesfalls trivial zu sein ...

Gruesse und vielen Dank

volkard

MADA schrieb:

Hi,
kennt jemand einen Algorithmus zur bildung der Potenzmenge? So dass man das ganze auch in einer Programmiersprache wie C++ umsetzen kann. Scheint mir nach dem ersten drueber nachdenken keinesfalls trivial zu sein ...
Gruesse und vielen Dank

doch, ist es.
wie soll die potenzmenge vorliegen? echt ne menge bauen? selten. eher üblich isses, du willst nur durch die gedachte potenzmenge iterieren. und dann ist noch fraglich, ob du die ganzen potentmengenelemente auch als mengen echt vorliegen haben willst oder auch nur durch diese iterieren.
am einfachsten ist es, wenn die grundmenge höchstens 32 elemente hat und dir der characterisctische string einer jeden menge reicht.
dann machste

//ungetestet
for(unsigned int i=0;i<(1<<menge.size());++i){
   cout<<"teilmenge "<<i<<": ";
   for(int j=0;j<menge.size;++j)
      if((1<<j)&i)
         cout<<' '<<menge[j];
   cout<<'\n';
}

volkard schrieb:

wie soll die potenzmenge vorliegen? echt ne menge bauen? selten. eher üblich isses, du willst nur durch die gedachte potenzmenge iterieren. und dann ist noch fraglich, ob du die ganzen potentmengenelemente auch als mengen echt vorliegen haben willst oder auch nur durch diese iterieren.

Hmm, die Menge soll eben als Potenzmenge vorliegen, das heisst als Menge von Mengen. Die Funktion soll also so aussehen:

vector<vector<T> > Potenzmenge (vector<T>) {...}

Guss

volkard

dann kannste meinen code nehmen und die potenzmenge zuzsammensammeln.

//ungetestet
vector<vector<T> > result;
for(unsigned int i=0;i<(1<<menge.size());++i){
   result.push_back(vector<T>());
   vector<vector<T> >::iteratir last=*result.rbegin();
   for(int j=0;j<menge.size;++j)
      if((1<<j)&i)
         last->push_back(menge[j]);
}

MamboKurt

vorschlag von mir:
wenn du eine menge mit n elementen hast, hat die potenzmenge 2^n elemente. diese kann man jeweils mit einer binärzahl von 0 bis 2^n-1 identifizieren:

M = {a, b, c, d, e}
Zahl: 10011
Teilmenge: {a, d, e}

also musst du einfach eine schleife machen die von 0 bis 2^n-1 geht und dann die entsprechende menge an deinen vector hängen.

vector<T> intToSubset(int n, vector<T> set)
{
  vector<T> temp;

  for(int i = 0; n < set.size(); i++)
  {
    if (n % 2 == 1)
      temp.push_back(set.at(i));
    n /= 2;
  }

  return temp;
}

vector< vector<T> > potenzmenge(vector<T> menge)
{
  vector< vector<T> > temp;

  for(int i = 0; i < pow(2, menge.size()); i++)
    temp.push_back(intToSubset(i, menge));

  return temp;
}

!! code ist nicht getestet !!

die lösung is vllt nicht die schnellste oder elganteste, aber ich denke dass sie recht anschaulich ist.

volkard

MamboKurt schrieb:

vorschlag von mir:
wenn du eine menge mit n elementen hast, hat die potenzmenge 2^n elemente. diese kann man jeweils mit einer binärzahl von 0 bis 2^n-1 identifizieren:

komisch, sowas hab ich schonmal gesehen.

MamboKurt

sry hab mir deinen code nicht genau durchgelesen. wollt halt auch mal schlau sein
da hab ich mir nun so viel mühe gegeben, nur um am ende festzustellen (wie is hier eigentlich die richtige rechtschreibung? "fest zu stellen" oder "festzustellen" oder "fest zustellen"), dass dein code das selbe macht nur schneller.
dein code is aber auch schon ausgefuchst

volkard

MamboKurt schrieb:

sry hab mir deinen code nicht genau durchgelesen. wollt halt auch mal schlau sein
da hab ich mir nun so viel mühe gegeben, nur um am ende festzustellen (wie is hier eigentlich die richtige rechtschreibung? "fest zu stellen" oder "festzustellen" oder "fest zustellen"), dass dein code das selbe macht nur schneller.
dein code is aber auch schon ausgefuchst

"festzustellen".
"fest zu stellen" ist auch erlaubt und nach alter neuer schreibe war es gefordert. das wurde zurückgenommrn, weil es zu viele fälle gab, wo einen bedeutungsunterschied hatte.
so, wie ob man das zuammen schreibt oder zusammenschreibt.