Kombinatorikproblem (Mathematiker/Informatiker gesucht)

Pronto451

Hallo Leute,

ich bräuchte da einen Ansatz für folgendes Problem.

Ich habe Zahlengruppen von 6 Zahlen.

Nun berechne ich alle möglichen 5er Gruppen, die z.B. mit 5 aus 30 Zahlen möglich sind. Diese 5er Kombinationen möchte ich dann zu so wenig wie möglichen 6er Kombinationen zusammen fassen.
Wie könnte ein entsprechender Algorithmus aussehen ?
(wenn möglich in C/C++ bitte)

Das gleiche Problem soll auch mit 4er, 3er, 2er Gruppen funktionieren, die aus einer Menge von bis zu 50 Zahlen erzeugt werden.

Pronto451

Walli

Klingt nach einem typischen Fall für einen Binomialkoeffizienten, oder?

nCr = (n! / (r! * (n-r)!)

Solltest du auf dem Taschenrechner finden.

Kannst Du etwas konkreter werden?
Also zum Anfang: Angenommen Du hast eine n-elementige Menge an Zahlen . Aus diesen Zahlen ziehst Du nun r Zahlen ohne zuruecklegen. Die Anzahl der Moeglichkeiten (unter der Voraussetzung, dass Du nur unterschiedliche (d.h. unterscheidbare) Zahlen hast) ist n ueber r, d.h.

MaSTaH schrieb:

Code:

nCr = (n! / (r! * (n-r)!)

Beispiel: Lotto: 6 ueber 45 ist ca. 14 000 000.

Pronto451 schrieb:

Diese 5er Kombinationen möchte ich dann zu so wenig wie möglichen 6er Kombinationen zusammen fassen.

Verstehe ich nicht. Willst Du immer 6 fuenfer Gruppen zusammenfassen? Oder einfach eine weitere Zahl anfuegen?

Pronto451

Hallo

nCr = (n! / (r! * (n-r)!)

So einfach ist es leider nicht.

Ein Beispiel :

6 aus 40 macht 3.838.380 mögliche Kombinationen
5 aus 40 macht 658.008 mögliche Kombinationen

Das Berechnen aller 5er Kombinationen kann man ja einfach mit einer verschachtelten for-Schleife erreichen.

Jetzt kommt aber das Problem. Ich brauche jetzt möglichst wenige 6er Kombinationen um damit alle 5er Kombinationen abzudecken.
In eine 6er Kombination bekomme ich ja 6 5er Kombinationen rein, wenn ich die jetzt aus allen möglichen 5er Kombinationen streiche muß ich die anderen auch irgend wie in weitere 6er Kombinationen rein bekommen. Da gibt es sicher überschneidungen, also 5er die doppelt/dreifach vorkommen. Gesucht ist aber ein Programmcode, der das optimiert.

Das Ganze sollte auch variabel sein, also 4 aus 30 oder 2 aus 25 usw.
Nur die 6er Kombis bleiben gleich.

Dazu einen Code zu finden ist das Problem.

Pronto451

Walli

Ja, jetzt ist die Aufgabenstellung klarer. Wenn mir was einfällt poste ich, ansonsten bin ich zu dämlich dafür .

rapso

bei "5 aus 40"
darf da ein element auch doppelt vorkommen?

rapso->greets();

Pronto451

Hallo rapso

bei "5 aus 40"
darf da ein element auch doppelt vorkommen?

Nein, das sind Kombinationen 5 aus 40 ohne zurücklegen.
Eben genau die 658.008 mögliche Kombinationen. bei doppelten Elemente währen das sehr viel mehr (Siehe z.B. Excel Funktion "Kombinationen").

Pronto451

SirLant

Irgendwie versteh ich das nicht, wie kommt man auf so viele Möglichkeiten?

Walli

Kannst es ja nachrechnen. Ist so .

SirLant schrieb:

Irgendwie versteh ich das nicht, wie kommt man auf so viele Möglichkeiten?

Ein Beispiel: 2 aus 10:

01 02 03 04 05 06 07 08 09
12 13 14 15 16 17 18 19
23 24 25 26 27 28 29 
34 35 36 37 38 39
45 46 47 48 49
56 57 58 59
67 68 69 
78 79 
89

=> 45 Moeglichkeiten. Es gilt aber auch 
    n!/(r!*(n-r)!) = 10!/(2!*8!) = 45

Die Anzahl der Moeglichkeiten waechst aber sehr schnell! Bei 3 aus 10 gibt es schon 120 Moeglichkeiten!

Pronto451 schrieb:

Dazu einen Code zu finden ist das Problem.

Ich habe ein bisschen nachgedacht, und bin gescheitert. Hast Du schon mal versucht dieses Problem bei einer leichteren Kombination zu loesen, d.h. 2 aus 10 mit Hilfe von 3 aus 10. Ist zwar aufendig, koennte aber die passende Idee liefern. Viel Erfolg!

ThAlb

Hallo!

Pronto451 schrieb:

nCr = (n! / (r! * (n-r)!)

So einfach ist es leider nicht.

Ein Beispiel :

6 aus 40 macht 3.838.380 mögliche Kombinationen
5 aus 40 macht 658.008 mögliche Kombinationen

Pronto451

Wieso ist es nicht so einfach?

Das sind doch die genau Werte die Du mit obiger Formel und n=40 und r=5 bzw. r=6 bekommst.

Wieviele Kombinationen sollten es denn Deiner Meinung nach sein?

Ich verstehe nicht wo der Unteschied zwischen Deiner Problemstellung und dem üblichen ziehen von r aus n Zahlen ohne Zurücklegen ist.

Viele Grüße
Th.

ThAlb schrieb:

Ich verstehe nicht wo der Unteschied zwischen Deiner Problemstellung und dem üblichen ziehen von r aus n Zahlen ohne Zurücklegen ist.

Ich glaube ich habe es verstanden: Aus irgendeinem Grund moechte Pronto451 Kombinationen von 6 Zahlen ziehen. Er/Sie moechte nun genau die Kombinationen bestimmen (der 6 Zahlen) die alle Kombinationen enthalten, die mit 5 Zahlen moeglich sind. Zum Beispiel braechte man (bei 2 bzw. 3 aus 10) fuer die 2er Kompis

01 02 12
nur die Kobi
012.
Die Kombi
123
enthaelt auch die 12 ist also nicht optimal (da die 12 zwei Mal vorkommt). Besser waere dann
134
da man dadurch auch noch die 14 und die 34 bekommt. Dann muss man sich aber ueberlegen, wei man die 23 erhaelt ...usw....usw...

Pronto451

Hallo benutzername

Er moechte genau das

Du hast es erfaßt, ich habe das schon mal auf dem Papier mit wenigen Kombinationen gemacht, aber daraus keinen Algorithmus ableiten können.
Vielleicht hat ja hier jemand zu dem Problem eine Mathematische oder Informatische Lösung.

Pronto451

WebFritzi

Ich glaub, ich hab da was für dich. Also, es wird schwer zu erklären. Ich habe einen speziellen Fall gewählt. Vielleicht ist es ein Ansatz für dich.

Beispiel: (3 aus 5 und 4 aus 5)

123    1234
124    1235
125    1245
134    1345
135    2345
145
234
235
245
345

Sehr wichtig ist, dass die Reihenfolge der Kombis durch die lexikographische Ordnung bestimmt wird. Also, fangen wir an. Der erste Block ist "1234". Darin sind enthalten "123, 124, 134, 234". Das kommt dadurch zustande, dass man zuerst den 4., dann den 3., dann den 2. und dann den 1. streicht. OK, das sind also schonmal 4 3-er-Kombis. Und was habe alle diese Kombis gemeinsam? Richtig: die 5 ist nicht dabei! Wir haben damit also alle 3-er-Kombis abgegrast, die keine 5 drin haben. Das ist nämlich der ganze Trick. Dadurch können wir nämlich die Odnung reduzieren und rekursiv fortfahren. Wir können jetzt nämlich die 5 komplett weglassen, da sie ja eh immer hinten steht. Nachher können wir sie ja wieder ranknüpfen. Nachdem wir aus der ersten 4-er-Kombi schon alles rausgeholt haben, sehen unsere Kombis jetzt so aus:

12(5)    123(5)
13(5)    124(5)
14(5)    134(5)
23(5)    234(5)
24(5)
34(5)

Bei diesem Bild wird jetzt alles klar, denn links sehen wir schön die 2 aus 4 - Kombis, während wir auf der rechten Seite die 3 aus 4 - Kombis sehen. Eigentlich sind wir damit fertig, aber ich will das doch noch zu Ende führen.
Wir nehmen uns wieder die erste 3-er-Kombi ("123"). Daraus lassen sich die 2-er-Kombis "12, 13, 23" machen. Mit der 5: "125, 135, 235". Diese Kombis haben wieder gemein, dass die 4 nicht dabei ist. Also wieder: 4 abschneiden, und es bleibt:

1(45)    12(45)
2(45)    13(45)
3(45)    23(45)

Aus "12" lassen sich "1" und "2" machen. Mit 4 und 5: "145, 245". Was übrig bleibt, ist:

(345)    1(345)
         2(345)

Aus der 1 lässt sich nun garnichts mehr machen. Fassen wir "garnichts" als leere Menge auf und alle Kombis als Mengen, dann passt uns das wieder in den Kram, denn dann bleibt

Ø u {3,4,5}

also {345}, oder in unserer bisherigen Notation: "345". Fertig!

Pronto451

Hallo WebFritzi

Danke für den Ansatz, jetzt werde ich mal versuchen das in einen Programmcode umzusetzen.

Auf dich kann man sich immer verlassen

Pronto451