4. menge von elementen auf bestimmte anzahl aufteilen

menge von elementen auf bestimmte anzahl aufteilen

  • X

    Hi,

    ich suche einen algorithmus der mir eine bestimmte anzahl von elementen auf eine bestimmte anzahl von mengen aufteilen.

    beispiel:

    ich hab 20 elemente die ich auf 5 mengen aufteilen möchte. gesucht sind jetzt
    alle mögliche kombinationen wenn immer alle 20 elemente verwendet werden müssen.
    also z.b.

    16|1|1|1|1
    15|2|1|1|1
    ...

    das ganze soll natürlich für eine beliebige anzahl von elementen und mengen funktionieren. hab mir da dazu zwar schon etwas überlegt aber eher kompliziert. vl hat das jemand schon einfacher gelöst 🙂

    lg

    0
  • J

    (nk)=n!(n−k)!k!\binom{n}{k} = \frac{n!}{(n-k)!k!}, der Binomialkoeffizient.

    0
  • I

    Wenn du nicht nur die Anzahl, sondern wirklich alle Elemente brauchst, dann probier am besten alle durch. Fang an bei 1|1|1|1|1 und höre auf bei 20|20|20|20|20.

    0
  • M

    Jodocus schrieb:

    (nk)=n!(n−k)!k!\binom{n}{k} = \frac{n!}{(n-k)!k!}, der Binomialkoeffizient.

    Nein, gesucht sind die Stirlingschen Zahlen zweiter Art. Aber ich glaube, es war eh nach einer Auflistung aller Möglichkeiten und nicht nach der Anzahl der Möglichkeiten gefragt.

    ipsec: Ich glaub, du hast seine Notation falsch verstanden. Die Zahlen repräsentieren die Anzahl der Elemente einer Teilmenge. Aber alle durchprobieren, ist hier natürlich der gesuchte Algorithmus.

    0
  • X

    genau ich wollte die auflistung aller möglichkeiten.
    na gut dann werd ich wohl alles durchprobieren müssen. hab gedacht
    das geht vl einfacher 🙂

    vielen dank

    0
  • O

    es geht zum Beispiel einfacher, wenn du nicht alle Möglichkeiten durchgehst, sondern nur die möglichen.

    Kann es sein, dass diese Frage in letzter Zeit in allen Variationen gestellt wird? Ich denke schon fast 3x in den letzten 2 Monaten.

    0
  • X

    es geht zum Beispiel einfacher, wenn du nicht alle Möglichkeiten durchgehst, sondern nur die möglichen.

    wie meinst du das? ich kann ja nur mögliche stellen durchgehen also:

    z.b.

    16 1 1 1 1
    15 2 1 1 1
    .
    .
    .
    1 1 1 1 16

    hab mirgedacht ich mach mal die erste stelle von 16 bis 1 und dann fang ich wieder von vorn an mit den weiten 4 stellen wo ich mir wieder die erste anschau.

    8 1 1 1
    7 2 1 1
    .
    .
    .

    wenn das schon so viele gefragt haben, gibts vl schon wo eine fertige lösung ?

    lg

    0
  • M

    Überleg dir mal eine rekursive Funktion:

    void möglicheKombinationen(vector<int> bisherigeMengengrößen, int anzahlVerbleibendeElemente, int anzahlVerbleibenderTeilmengen);

    Das solltest du hinbekommen 🙂

    0
  • X

    bin mir sicher dass ich das hinbekomme 🙂 mit testen usw geht trotzdem zeit drauf und wieso nochmal was erfinden was vl anderswo schon funktioniert 🙂

    0
  • X

    ich glaub ich war wohl etwas zu voreilig. hab versucht das ganze rekursiv aufzurufen aber irgendwie überschreibts mir mein array. vl geh ichs auch nur zu kompliziert an. hat vl jemand eine konkrete idee?

    0
  • M

    Wie sieht denn dein bisheriger Code aus?

    0
  • X

    hi,

    habs jetzt geschafft danke. hab den speicher jetzt dynamisch angefordert damit wars leichter.

    danke für die hilfe 🙂

    0
  • O

    xxmaxx schrieb:

    hi,

    habs jetzt geschafft danke. hab den speicher jetzt dynamisch angefordert damit wars leichter.

    danke für die hilfe 🙂

    na, wenn das mal gut geht...

    0
Anmelden zum Antworten