Folge von Mengen verwalten

Hallo zusammen,

ich möchte gerne eine Folge von Partitionen der Menge {0,1,...n} verwalten, also etwas in dieser Form: (({0,1,2},{3,4,5}),({2,4,0},{5,1,3}),...).

Relevant ist die Reihenfolge der Partitionen sowie die Reihenfolge der Teilmengen. Im Programm wird eine solche Liste nicht mehr geändert, wenn sie einmal erstellt wurde. Es muss aber für jede Partition aus der Liste schnell entschieden werden, in welcher Teilmenge eine vorgegebene natürliche Zahl k liegt.

Ich suche einen geeigneten Datentyp.

Wie wäre es mit einem verschachtelten Array und set aus der STL für die Teilmengen?

Grüße, Apollo

Seecho schrieb:

Wie wäre es mit einem verschachtelten Array und set aus der STL für die Teilmengen?

Erfüllt das deine Anforderungen?

theta

#include <array>
#include <vector>

typedef std::array<int, 3> triple;

int main()
{
   std::vector<triple> v = { { 0, 1, 2}, { 3, 4, 5 } };
}

http://channel9.msdn.com/Events/Build/2014/2-661

Columbo

ich möchte gerne eine Folge von Partitionen der Menge {0,1,...n} verwalten, also etwas in dieser Form: (({0,1,2},{3,4,5}),({2,4,0},{5,1,3}),...).

Am besten speicherst du einfach ganze Partitionen in einem Container und unterscheidest dann zwischen Untermengen dieser Partitionen im Code. Kannst natürlich auch start/end Iteratoren auf diese Untermengen per Zeigerarithmetik bekommen.

Steht die Größe (oder gar Anzahl) der Partitionen schon zur Compile-Zeit fest? Dann kannst du seit C++11 std::array , oder mit C++98 ein echtes Array bzw. selbstgebastelten Wrapper nehmen, sonst, falls nichts dagegen spricht, vector .
Also so etwa in der Richtung

std::vector<std::array<std::uint8_t, 6>> mPartitions;

Seecho schrieb:

Ich suche einen geeigneten Datentyp.

Eine map?
Ich speichere zu jeder Zahl die Indices der Teilmengen in denen diese vorkommt.

#include <map>
#include <iostream>
#include <vector>
#include <initializer_list>

class partitionlist{
public:
  using subset = std::vector<int>;
  using partition = std::vector<subset>;

  partitionlist(std::initializer_list<partition> l)
    :data_(l)
  {
    for(const auto& p : data_){
      int ix = 0;
      for(const auto& ss : p){
	for(auto i : ss)
	  lut_[i].push_back(ix);
	++ix;
      }
    }
  }

  const subset& operator()(int i, int j) const {
    return data_[i][j];
  }

  std::vector<size_t> find(int i)
  {
    return lut_[i];
  }
private:
  std::vector<partition> data_;
  std::map<int, std::vector<size_t>> lut_;
};

std::ostream& operator<<(std::ostream& out, const partitionlist::subset& ss)
{
  for(auto i: ss)
    out << i << ' ';
  return out;
}

int main(){
  using namespace std;
  partitionlist l = {{{0,1,2},{3,4,5}},{{2,4,0},{5,1,3}}};
  auto ixs = l.find(5);
  int i=0;
  for(auto j : ixs){
    std::cout << l(i,j) << '\n';
    ++i;
  }
}

Die Formatierung ist für'n Müll...sei's drum.

volkard

Gelöscht, hatte Quatsch gelesen.

Bashar

*** Korrektur obsolet. ***

Hi, danke fuer die Antworten, insbesondere an Arcoth und Furble Wurble! Habe mir naemlich jetzt ueberlegt, es mit map zu machen.

Jester

Ich hätte jetzt vorgeschlagen eine partition als vector<int> zu kodieren, wobei der v[i] sagt in der wievielten teilmenge der partition das i drin ist. Kommt aber natürlich auch drauf an was du damit genau vor hast.