Wie sortiert mam am effektivsten paarweise? Ansatz richtig?

freshman_Jörg

Ich habe verschiedene Objekte einer Klasse. Diese Objekte werden durch das Programm automatisch aus einer Datei eingelesen und dabei erzeugt. Die Objekte können einer vorher nicht bekannten Anzahl von Kategorien zugeordnet werden (von 0 bis unbekannt). Die Objekte haben weiterhin eine Eigenschaft (z.B. ALter).

Ziel: Das Programm soll am Ende alle Objekte zu Zweier-Teams zusammengefasst haben, wobei immer nur Objekte der gleichen Kategorie in ein Team dürfen. Die Teams sollen am Ende nach dem Durchschnittsalter sortiert sein.

Wie löst man dieses Problem am effektivsten?

Ich wollte ursprünglich alle Teams der gleichen Kategorie in einem seperaten Vektor "Kategorievektor" zusammenfassen (hätte dann so wiele Kategorievektoren wie Kategorien) und diese "Kategorievektoren" dann nach dem Alter sortieren. Dann wollte ich für die ersten zwei Objekte eines jeden "Kategorievektor" das Durchschnittsalter berechnen lassen. Bei dem "Kategorievektor" mit dem geringsten Durchschnittsalter der ersten zwei Objekte, wollte ich die ersten zwei Objekte entfernen und dem "Lösungsvektor" zuordnen.
Dann das Verfahren solange durchlaufen, bis alle Objekte auf dem "Lösungsvektor" verplant sind. Dabei verringern sich die jeweiligen "Kategorievektoren" natürlich.

Mein Problem:
Ich weiß im Vorfeld natürlich nicht, wie viele "Kategorievektoren" ich einlesen werden. Gibt es eine Möglichkeit die Vektoren automatisch zu bennenen und später mit den automatischen Namen weiterzuarbeiten (durch Schleifen etc?) - Wenn ja - kann mir jemand einen Tipp geben, wo ich ein Bsp. finde bzw. wo ich suchen muss.

Ein anderer Ansatz wäre auch gut. Mir geht es hier nicht darum, dass mit jemand den kompletten Code schreibt (macht sowieso niemand und ich bin ja nicht faul), sondern lediglich um Tipps für mein vorgehen.
Ich selber habe mal wegen der übersichtlichkeit mal auf meinen C++ Code verzichtet, der würde hier nicht weiterhelfen, da es mir zum einem um eine "Bewertung" meines geplanten Vorgehens geht und zum anderen ich überhaupt keinen Plan hab, wie ich die Vektoren automatisch benennen kann. Meine erste Idee war:

int hilfsvariabe = 0;
for (int i=0; i<Kategorie; i++, hilfsvarable++)
{
    vektor <Klasse> hilfsvariable;  // ich kann natürlich keinen Vektor mit einer integer Veariablen benennen - funzt jedenfalls nicht 
}
    // späterer Aufruf durch:
    hilfsvariable[0].getMethode

Ich wäre für jeden Tipp dankbar und bitte lacht nicht zu laut über meinen Ansatz

Meep Meep

hallo

ich wuerde zuerst alle nach kategorie sortieren. dann von anfang bis ende immer 2 klassen vergleichen ob selbe kategorie ist. dann in eine der beiden klassen das alter der anderen dazu addieren und durch 2 teilen. die klasse in einen neuen vector speichern und zu den naechsten 2 klassen weiterruecken. das machst du bis du am ende bist. dann brauchst du nur noch den anderen vector sortieren und fertig.

HarteWare

Hallo,

EDIT: Hab jetzt mal genauer gelesen, mein Post ist nicht ganz so hilfreich

ich hab deinen Beitrag nicht so genau durchgelesen, weil müde. Aber was du beschreibst klingt in meinen Ohren verdamt nach

map<int, vector<Data>> objects;

Dazu ein nicht sehr schönes Beispiel, das musst du natürlich anpassen bzw. verbessern:

struct Data {
   int category;
   int age;
};

std::istream& operator>>(std::istream& is, Data& data)
{
    is >> data.category >> data.age;
    return is;
}

int main()
{
    using namespace std;

    map<int, vector<Data>> objects;
    ifstream file("data.txt");
    if (!file) {std::cerr << "File not found\n"; return 1;}
    Data data;
    while (file >> data) {
        objects[data.category].push_back(data);
    }
    for (auto& cat : objects)
        sort(cat.second.begin(), cat.second.end(), [] (const auto& left, const auto& right) {
            return left.age < right.age;
        });

    for (const auto& cat : objects) {
        cout << "Category " << cat.first << ":\n";
        for (const auto& obj : cat.second)
            cout << "    " << obj.age << '\n';
    }
}

data.txt

output:

Category 1:
    19
    35
Category 2:
    29
Category 12:
    43

hustbaer

@freshman_Jörg
Du kannst Vektoren auch verschachteln:

vector<vector<Klasse>> kategorien;

// Mit kategorien[0] bekommst du den vector<Klasse> für die 1. Kategorie
// Mit kategorien[0][41] bekommst du das 42. "Klasse" Objekt der 1. Kategorie

Dann kannst du einfach Teams bilden und die z.B. in einem vector<Team> speichern. Den vector<Team> kannst du dann anhand des Durchschnittsalters sortieren.

Das wäre der Ansast der mMn. am ehesten dem entspricht wie du es dir ursprünglich vorgestellt hast. Zumindest wenn ich dich richtig verstanden habe.

Gibt es eine Möglichkeit die Vektoren automatisch zu bennenen und später mit den automatischen Namen weiterzuarbeiten (durch Schleifen etc?)

S.o.
Als Ergänzung: Bei den einzelnen Objekten der selben Kategorie könnte man ja die selbe Frage stellen. Also ob man die einzelnen Objekte irgendwie automatisch benennen kann und dann über diesen automatischen Namen zugreifen. Kann man nicht, aber man kann mehrere Ding -e in einen vector<Ding> stecken. Soweit war dir das ja schonmal klar. Und die selbe Lösung wie für mehrere Ding -e kann man für mehrere vector<Ding> -e verwenden. Ein vector<Ding> ist ja auch bloss ein Objekt. Und damit wären wir dann bei vector<vector<Ding>> .

Und falls du mal Strings (oder andere Objekte) als "Name" brauchst, auch dafür gibt es was. Das meisst dann map . z.B. map<string, Ding> . Das verwendet dann einen String als "Name" (Key) und legt unter diesem Namen ein Ding am (Value).

HarteWare

Dong

Hallo, ich denke, dass sich das Problem recht einfach mit einer Multimap lösen lässt. Dort kannst du als jeweiligen Key das angeben, was die Kategorie für dich ausmacht, brauchst dann also nicht unbedingt mit einer int-Variable arbeiten wie in dem Beispiel mit den verschachtelten Vektoren. Vielleicht reicht dir das aber ja auch schon.

http://www.cplusplus.com/reference/map/multimap/

LG

freshman_Jörg

Ich danke euch allen erstmal - kann jetzt erstmal fleißig weitermachen