Kombinatorik-Problem: Optimierte Auswahl von Zutaten

[himitsu]

nee nee, das mit den 20 hatte ich nur falsch gelesen/verstanden.


da könnte man ja zuerst mal eine Liste zusammenstellen, welche die mglichen Kombinationen aus maximal 20 Zutaten enthält ... aber da dürfte es schneller sein, wenn man über die Rezepte geht und über deren nötigen Zutaten diese Liste erstellt ... die 20000 2000 Rezepte dürften schneller abgearbeitet sein, als alle 2^100 Zutatenkombinationen.

und dann die gefundenen Kombinationen nochmal aufarbeiten (falls sie aus den Rezepten entstanden), so daß auch Kombinationen aus je "genau" 20 Zutaten entstehen

und dann die entstandene Liste nochmal durchgehn und die Rezepte zählen.

[Satty67]

Wieviele Zutaten hat den im Durchschnitt so ein Rezept.. eher 5, 10 oder 15 oder sogar über 20 und der Rest muss von Hand beigemischt werden?

[franktron]

Also eine Lösung die zu >90% richtig ist.

Man suchte die Zutat die am meisten vorkommt dann sucht man im Ergebnis wieder die am meisten vorkommende Zutat u.s.w.

Das Problem ist ob die am meisten vorkommende Zutat auch die meisten Rezepte bringt,
mann kann das aber noch mit Platz 2-10 Testen.

[jfheins]

Zitat von franktron:

Also eine Lösung die zu >90% richtig ist.

Man suchte die Zutat die am meisten vorkommt dann sucht man im Ergebnis wieder die am meisten vorkommende Zutat u.s.w.

Das Problem ist ob die am meisten vorkommende Zutat auch die meisten Rezepte bringt,
mann kann das aber noch mit Platz 2-10 Testen.

Diese Lösung kann dazu führen, dass man von allen Rezepten ein paar Zutaten hat, aber für kein Rezept alles. Wär dann auch irgendwie doof ...

[Satty67]

Eine abschließende Frage hab' ich noch.

Gibt es wirklich so viele Kombinationen bei 20 aus 100? Darf ja keine Permutation dabei sein. Also 100^20 Kombinationen?

[jfheins]

100 über 20 ist 5,36 * 10^20 ("Kombinationen" - Also die Möglichkeiten, aus einer Menge von 100 Elementen 20 herauszunehemen ohne Beachtung der Reihenfolge)

Mit Beachtung der Reihenfolge ("Variation") sind es 1,3 * 10^39

interessant dazu auch das hier: http://de.wikipedia.org/wiki/Kombinatorik Für die Anzahl der Möglichkeiten mit/ohne Beachtung der Reihenfolge ohne Zurücklegen

[guidok]

Zitat von Daniel G:

Zitat von Satty67:

Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

Und wenn man ne Liste mit den 20 häufigsten Zutaten erstellt, und dann alle Rezepte auflistet, in denen nur Zutaten aus dieser Kategorie auftauchen? Dann müssten das doch imho die gesuchen sein, oder?

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier...

Ich könnte mir folgende Frage vorstellen: Welche 20 Zutaten brauche ich, um möglichst viele Cocktails mixen zu können?

[Satty67]

Zitat von jfheins:

interessant dazu auch das hier: http://de.wikipedia.org/wiki/Kombinatorik Für die Anzahl der Möglichkeiten mit/ohne Beachtung der Reihenfolge ohne Zurücklegen

Ja, Danke... gibt halt ein paar Bereich in der Mathematik, die nicht wirklich zu meinen Stärken gehört.

[Draos]

Meine Idee wäre eine Liste mit der Häufigkeit jeder Zutat. Die Rezepte, in denen die häufigsten Zutaten vorkommen, sollten dann vervollständigt werden. Wenn noch Zutaten übrig sind nächste Ebene von Rezepten (weniger häufige Zutaten) nehmen. Wäre ne Idee spart auch Rechenleistung, aber ob es die Optimale ist kA.

[franktron]

Zitat von Draos:

Meine Idee wäre eine Liste mit der Häufigkeit jeder Zutat. Die Rezepte, in denen die häufigsten Zutaten vorkommen, sollten dann vervollständigt werden. Wenn noch Zutaten übrig sind nächste Ebene von Rezepten (weniger häufige Zutaten) nehmen. Wäre ne Idee spart auch Rechenleistung, aber ob es die Optimale ist kA.

Genau so meinte ich das auch.

Hab mich wohl etwas undeutig ausgedrückt