Kombinationen



  • Moin

    Ich suche nach nem Algo der mir folgendes liefert...

    Sei A eine Menge und n eine Zahl kleiner Anzahl Elemente der Menge...

    Nun will ich alle Kombinationen (Reihenfolge egal und keine Doppelten) für ein beliebiges n haben die beim 1 bis n mal ziehen ohne zurücklegen entstehen können...

    Gibts da schon was fertiges in c++ ?



  • Wenn die Menge nicht zu gross ist.
    std::vector füllen
    next_permutation auf Vecktor anwenden
    ersten N Elemente nehmen.
    ansonsten

    while (vector.size()<n)
    {
     val = rand();
     std::vector::const_iterator pos=std::find(vector.begin(),vector.end(),val);
     if( pos==vector.end()) vector.push_back(val);
    }
    


  • willst du die anzahl oder einen iterator als ergebnis?



  • Ich glaub ich habe meine Frage unverständlich formuliert und probier es gleich nochmal ganz anders mit dem eigentlichen Ziel wo ich hin will...

    Angenommen ich habe eine Menge mit n verschienenden Elementen.

    Nun geht es um Auteilen der Elemente der Menge. Beim Aufteilen muss jede Menge immer mindestens 1 Element enthalten.

    Jetzt will ich mir ne Funktion basteln die mir zunächst alle Kombination bastelt mit der sich aus der obigen Menge genau eine Menge basteln lässt..

    In dem Fall trivial denn es gibt nur eine...

    Jetzt das ganze für genau zwei Mengen. Also alle Kombinationen wie ich die Elemente auf die beiden Mengen aufteilen kann...

    Dann das ganze für drei Mengen bis mit n Mengen wieder der triviale Fall erreicht ist...



  • was soll der typ des rueckgabewertes der funktion sein? suchst du nach der anzahl der funktionen oder nach einem array von sets?



  • @PeterTheMaster

    Ist mir vom Prinzip her egal.. Wichtig ist mir eher das ich alle Kombinationen erwische. Was man machen könnte wäre ja z.B. eine std::list<std::vector<char>>

    ein std::vector<char> wäre dann eine kombination...

    also z.B. 0 1 0 0 0 würde mir sagen 1.3.4.und 5. Element in Menge 0 und 1. in Menge 1

    Mein Problem ist auch weniger das programmieren sondern eher das Algo dafür als solches...



  • und mein problem war bisher, dass ich nicht wusste, ob du nur die anzahl willst, oder wirklich alle moeglichkeiten irgendwie repraesentiert. zwoteres kann ziemlich speicherintensiv werden, wie dir ersteres schnell verraet. von daher waere vielleicht ein iterator besser.

    also nochmal dein problem: du hast eine menge mit n elementen und willst alle moeglichen k-elementigen partitionen von n durchlaufen, richtig? ich fuerchte da wird es keinen wirklich eleganten algo geben, erst recht, wenn du doppelte ausschliessen willst. wofuer genau brauchst du das denn? vielleicht laesst sich das huebscher loesen.



  • Ich will bestimmte Kombinationen nach vorher festgelegten Kriterien bewerten. Dafür ist es also gar nicht notwendig auch alle Kombinationen zu speichern sondern nur die, die mich interessieren oder eine hohe Bewertung erzielen. Problem bei der Sache ist dann ggf. dafür zu sorgen, dass auch alle möglichen Kombinationen durchlaufen werden... Es wird wenn dann ein Problem von der Rechenleistung weniger des Speichers...

    Aber vom Prinzip her würde mich auch die zunächst mal die Anzahl interessieren. Hast du da ne Formel auf der Pfanne. Imho müsste das ja irgendwie noch polynominell (und damit nicht ganz so schlimm) sein...



  • Ne, das wird exponentiell. Für 2 Päckchen der Größe n/2 hast Du schon n über n/2 Möglichkeiten, das ist

    n!/((n/2)!(n/2)!) = n(n-1)...(n/2+1)/((n/2)(n/2-1)...*1) = n/(n/2) * (n-1)/(n/2-1) * ... * (n/2+1)

    Jeder der Faktoren liegt etwa in der Gegend von 2 der Gesamtausdruck hat damit ungefähr einen Wert von 2^(n/2)

    Bruachst Du wirklich die beste Anordnung? Dann kommst Du vermutlich um's ausprobieren aller Varianten nicht herum. Oder reicht Dir eine gute bis sehr gute Lösung?



  • @Jester
    Ich habe da eine kleine Einschränkung ganz vergessen zu erwähnen 🙄

    Für mich macht es keinen Unterschied in welche Menge ich Element x einordenen...

    Nehmen wir mal an ich habe n Elemente und verteile diese auch auf n Mengen. Von Prinzip her gäbe es dafür ja n! Möglichkeiten. Für mich wäre es aber nur eine da es mir konkret egal ist zu welcher Menge die einzelnen Elemente gehören. Ich will nur alle Kombinationen haben wie ich quasi Elemente zusammenfassen kann. Ob diese dann in Untermenge a oder b liegen ist mir egal..

    Ich versuch das ganze mal an einem Beispiel zu erklären..

    Nehmen wir mal an ich hätte als Menge 1,2,3,4,5,6,7

    So das mit in eine Menge zusammenpacken ist trivial... Es gibt nur eine Möglichkeit...

    Jetzt kommt 2 Mengen:

    1 und 2,3,4,5,6,7
    2 und 1,3,4,5,6,7
    3 ....
    4 ....
    5 ....
    6 ....
    7 ....

    dann noch (1,2) (3,4,5,6,7) bis (1,7) (2,3,4,5,6)
    (2,3) (2,4,5,6,7) bis (2,7) (1,3,4,5,6)
    bis (6,7) (1,2,3,4,5)

    dann die 3er (1,2,3) (4,5,6,7) bis (1,2,7) (3,4,5,6)
    (1,2,4) (3,5,6,7) bis ....
    .
    .
    .

    (5,6,7) (1,2,3,4)

    so und ab den 4ern interessieren die mich nicht mehr weil ich die gleichen mengenkombinationen bekomme...

    denn (1,2,3,4) (5,6,7) habe ich ja schon bei den 3ern (5,6,7) (1,2,3,4) abgefakelt. Das macht für mich keinen unterschied bzw dieses sollen äquivalent sein...

    So daher hatte ich als Ansatz für die Komplexität bisher:

    1 für die EinserMengen

    für die 2er Mengen:
    n für 1 und (n-1)er Kombinationen
    Summe(n-1) für 2 und (n-2)er Kominationen
    bis (n/2)abgerundet und (n/2)aufgerundet er Kombinationen

    und daher sah mir das ganze irgendwie polynominell aus...



  • Windalf schrieb:

    @Jester
    Ich habe da eine kleine Einschränkung ganz vergessen zu erwähnen 🙄

    Für mich macht es keinen Unterschied in welche Menge ich Element x einordenen...

    Nehmen wir mal an ich habe n Elemente und verteile diese auch auf n Mengen. Von Prinzip her gäbe es dafür ja n! Möglichkeiten. Für mich wäre es aber nur eine da es mir konkret egal ist zu welcher Menge die einzelnen Elemente gehören. Ich will nur alle Kombinationen haben wie ich quasi Elemente zusammenfassen kann. Ob diese dann in Untermenge a oder b liegen ist mir egal..

    Das hilft trotzdem nicht viel. Alleine das Beispiel von oben mit zwei gleichgroßen Mengen. Dort wird jede Zerlegung zweimal gezählt. Du mußt also nur noch durch 2 teilen und hast die Anzahl. 2^(n/2 -1) ist leider immer noch exponentiell.

    Das ganze sieht mir auch sehr exponentiell aus. Es würde micht ehrlich gesagt sehr wundern, wenn die Anzahl polynomial wäre.



  • beschreib doch dein problem mal weiter. was sind die menge? wonach willst du die tielmengen bewerten? vielleicht gibts ja einen besseren als den brute force ansatz.



  • Ich glaube zunächst einen anderen (besseren Lösungsasatz gefunden zu haben) und werds erstmal damit weiter probieren (auch wenn mir das nicht ganz so gut gefällt da ich dann nen Solver quälen werde 😃 )

    Wenn ich mich doch entscheiden sollte den alten Ansatz weiter zu verfolgen meld ich mich wieder...

    Danke greetz Windi


Log in to reply