Alle möglichen Kombinationen von Vektoren



  • Hallo Zusammen,

    ich möchte ein C++ Programm schreiben, in dem alle möglichen Kombinationen von vier Basis-Vektoren (Dimension 4) berechnet werden. Wiederholungen sind erlaubt.

    Was die Sache für mich schwierig macht, ist dass der Benutzer eine Anzahl von Vektoren eingibt. Ich weiß also nicht im Voraus, wie viele for-loops ich benötige.

    Weiterhin soll jede Kombination einzeln in einer 4xN Matrix gespeichert und ausgegeben werden, wobei die Vektoren dann die Spalten der Matrix bilden.

    Da ich in C++ noch Anfänger bin, freue ich mich über jede Hilfe.

    Gruß,
    Frank 🙂



  • Was verstehst du in dem Zusammenhang unter "Kombinationen"?

    Ansonsten: Wenn du nicht weißt, wie tief du schachteln mußt, kannst du es mal mit Rekursion versuchen. Alternativ kannst du auch alle Zahlen von 0 bis 4n durchgehen und zur Basis 4 aufschlüsseln (die Ziffern kannst du als Index in das Array der Basisvektoren verwenden).



  • Angenommen, Du veränderst das Problem auf alle Kombinationen von std::string, würde eine Lösung davon Dir dein Hauptproblem lösen?
    (Weil, dann wäre es einfacher für Helfer, man müßte sich nicht erst über die 4D-Vektoren einigen.)
    Kannst Du eine main() liefern, die eine hypotetische Funktion Aufruft, die alle Kombinationen anzeigt?
    Sind es nicht unendlich viele Kombinationen?



  • Mit Kombinationen meine ich, wenn die Basis-Vektoren z.B.

    1,2,3,4 hießen und der Benutzer gibt 3 ein, dann sind:

    111
    112
    113
    114
    121
    131
    .
    .
    .
    444

    die möglichen Kombinationen.

    mit Rekursion versuchen

    Rekursion ist immer so eine Sache. Wie gesagt, ich bin noch nicht so geübt. Mir fehlt momentan noch der Blick dafür.

    alle Zahlen von 0 bis 4n durchgehen und zur Basis 4 aufschlüsseln

    Diese Idee werde ich mal genauer betrachten.

    Kannst Du eine main() liefern, die eine hypotetische Funktion Aufruft, die alle Kombinationen anzeigt?

    Nein, eine main() habe ich noch nicht.

    Angenommen, Du veränderst das Problem auf alle Kombinationen von std::string,

    Da ich später mit den Vektoren noch weiterrechnen muss erscheint mir das nicht so praktisch, aber man könnte ja jeden Buchstaben später wieder mit dem Vektor identifizieren. Was würdest Du denn mit strings machen ?



  • siehe oben:

    Möglichkeit 1: rekursiv
    Eine n-stellige Kombination besteht aus einem beliebigen Basisvektor und einer (n-1)-stelligen Kombination (die du wieder nach dem selben Schema ermitteln kannst).

    Möglichkeit 2: numerisch
    Wenn du die Bezeichnungen änderst auf 0..3, siehst du, daß du dort alle Zahlen zur Basis 4 hast - den Weg kannst du auch rückwärts gehen:

    vector<vector<Element> > data;
    for(int z=0;z<hoch(4,n);++z)
    {
      vector<Element> v;
      int z2 = z;
      for(int i=0;i<n;++i)
      {
        v.push_back(Basis[z2%4]);
        z2/=4;
      }
      data.push_back(v);
    }
    


  • CStoll schrieb:

    Möglichkeit 1: rekursiv
    Möglichkeit 2: numerisch

    Welche Möglichkeit ist effizienter und schneller?
    Die Matrizen werden später ziemlich groß.

    vector<vector<Element> > data;
    

    Mit dem STL-Container "vector" kenne ich mich kaum aus.

    Dass ein Vektor von Vektoren eine Matrix ergibt, läuchtet mir schon ein, aber was bedeutet "Element" ?

    Weiterhin benötige ich in meinem Programm:
    1. Matrix-Multiplikation
    2. Tensor-Produkt bzw. Direktes Produkt auch mehrerer Matrizen (z.B. der möglichen Kombinationen aus den vier Vektoren).
    3. Matrix-Transposition
    4. Einfügen einer SubMatrix in eine bestehende Matrix. Z.B. Einfügen einer 2x2 Matrix unterhalb einer vorgegebenen Zeile einer 12x2 Matrix

    Wie kann ich das alles möglichst effektiv implementieren? Gerade die Tensor-Produkte führen ja zu sehr großen Matrizen. Ich möchte keine Matrix-Bibliothek verwenden. Die hatte ich nämlich vorher schon und jetzt will ich alles ohne Library hinbekommen, weiß aber nicht wie, da ich mich mit der STL vector noch nicht so beschäftigt habe.

    Danke für die Hilfe, 🙂
    Frank



  • Frank1978 schrieb:

    CStoll schrieb:

    Möglichkeit 1: rekursiv
    Möglichkeit 2: numerisch

    Welche Möglichkeit ist effizienter und schneller?
    Die Matrizen werden später ziemlich groß.

    Da bin ich leider überfragt - im Zweifelsfall mußt du das beides umsetzen und messen, was schneller geht.

    vector<vector<Element> > data;
    

    Mit dem STL-Container "vector" kenne ich mich kaum aus.

    Dass ein Vektor von Vektoren eine Matrix ergibt, läuchtet mir schon ein, aber was bedeutet "Element" ?

    Du wolltest Kombinationen von Gegenständen haben, damit ist "Element" was immer du als Basisobjekte kombinieren willst. vector<Element> verwende ich hier als Auflistung von diesen Basisobjekten, d.h. als eine der ermittelten Kombinationen, vector<vector<Element>> zur Sammlung aller gefundenen Kombinationen.

    vector<> ist in C++ ein dynamisch verwaltetes Array, das recht wenig mit Vektoren im mathematischen Sinn zu tun hat. Für mathematische Anwendungen benötigst du vermutlich eine Spezialbibliothek außerhalb des C++ Standard - oder mußt es selber neu programmieren. (eventuell könnten einige Vektor/Matrix-Operationen mit std::valarray abgebildet werden, aber da bin ich mir nicht sicher)


Log in to reply