Alle Teilmengen einer Menge ermittlen

Ich habe einen vector<T> und will eine Schleife schreiben, die über alle Teilmengen des vector's iteriert (also ein vector<map<T,bool>> erstellt). Wie mache ich das am einfachsten?

Skym0sh0

Was die map<T, bool> damit zu tun hat versteh ich nicht ganz.

Aber teil dein Problem auf.

Erzeuge aus deinem Startvektor erstmal eine Liste, die alle Teilmengen enthält: Da sollte dann ein vector<vector<T>> rauskommen. Und da kannst du dann drüber iterieren.

Was hast du denn vor damit?

daddy_felix

wie soll denn die map aussehen? Eine Teilmenge von vector<T> wäre intuitiv wieder ein vector<T>. Somit wäre die Menge aller Teilmengen vector<vector<T>>.

BTW: std::set gibts auch...

eine Teilmenge M von einem vector<T> ist gegeben durch eine map<T,bool> TM mit TM[m] == true, genau dann, wenn m in M liegt.

Skym0sh0 schrieb:

Erzeuge aus deinem Startvektor erstmal eine Liste, die alle Teilmengen enthält:

Das war gerade meine Frage, wie das geht?

camper

Enthält der vector<T> Duplikate?

Nein.

knivil

Eine Map zu benutzen ist unguenstig. Ich wuerd ein Bitset/Integer benutzen und inkrementieren. Bit i gibt an, ob das i-te Element der Teilmenge ist. Ein uint64_t sollte reichen, da du ueber die Potenzmenge einer Menge M mit |M| > 64 nicht iterieren moechtest.

daddy_felix

hmmmmmmmm schrieb:

eine Teilmenge M von einem vector<T> ist gegeben durch eine map<T,bool> TM mit TM[m] == true, genau dann, wenn m in M liegt.

was ist das denn für ein Käse? Warum so umständlich?

camper

Ohne Rücksicht auf Effizienz, Eleganz, usw. hingeschrieben. völlig ungetestet.

map<T,bool> subset(const vector<T>& elems, uint64_t x)
{
    map<T,bool> result;
    for ( uint64_t i = 1, j = 1ull << elems.size(); i < j; i <<= 1 )
        result[elems[i]] = ( x & i ) != 0;
    return result;
}

vector<map<T,bool>> powerset(const vector<T>& elems)
{
    assert( elems.size() < 64 ); // sonst werden wir sowieso nicht fertig
    vector<map<T,bool>> result;
    for ( uint64_t i = 0, j = 1ull << elems.size(); i < j; ++i )
        result.emplace_back(subset(elems, i));
    return result;
}