Tach,

ich würde gern wissen, wie man vorgehen muss wenn man sogannte listen kombinationen berechnet.
Was ich damit meine, ihr habt ne liste mit beispielsweise 10 einträgen als checklistbox:



Was er nun machen soll, ist einfach alle möglichkeiten durchgehen welche man markieren kann und dann jede einzelne kombination speichern:

Würde so aussehen:

Kombination 1:



Kombination 2:



Kombination 3:



Kombination 11:



Kombination 12:



Kombination 13:



Kombination 20:




Kombination 20:



usw.

So lange halt bis alle kombinationen durch sind.

Ich hab absolut kein plan wie ich bei sowas vorgehen soll.

Wäre echt dankbar für vorschläge.

Thx,
Final[/code]

Iterativ
Nein, wirklich. bei einer Liste mit n Elementen gibt es 2^n Kombinationsmöglichkeiten. Du kannst also in einer Schleife von null nach 2^n-1 laufen und dann die ersten n Bits der Schleifenvariable auswerten. Wenn Bit k gesetzt, dann muss Listeneintrag k in das aktuelle Ergebnis.
z.B.: 15. Durchlauf:
Bits der Schleifenvariable (links niederwertig) 1111000000000000000 (sinds 32?)
=> Eintrag 1,2,3 und vier müssen in das 15. Ergebnis

22. Durchlauf:
Bits der Schleifenvariable: 01101000000000...
=>Eintrag 2,3 und 5 müssen ins Ergebnis.

Alle Ergebnisse schreibst Du dann in Deine Ergebnisliste.

p.s. ob Bits gesetzt sind, prüfst Du in einer zweiten Schleife mit
,
wobei Loop2 von 0 bis n läuft.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Wenn ich sowas sehe sträubt sich mir irgendwie alles.

Was ist dein Ziel? Sag mal um was es genau geht. Eventuell gibt es eine wesentlich pfiffigere Lösung als einen 2^n Algorithmus (Was wahrscheinlich ist).

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ziel ist es nen tool zu bauen, welches die besten ergebnisse erzielt auszugeben, welche ordner am besten auf ne DVD passen.

Dann hast du hier schon die Weg zur perfekten Lösung genannt bekommen.
Einzig für die Laufzeit ist es miserabel. Hier solltest du einen Algorithmus mit optimaler Lösung suchen.

Ansonsten bist du als Mensch schneller

Für sowas sollte es Patentlösungen geben. Schließlich ist die Hauptspeicherverwaltung in Betriebssystemen ähnlich aufgebaut.

Is aber wirklich ein blödes Problem. Ob es in der TI für sowas einen standard-Algorithmus gibt? Ich frag mal einen unserer Übungsleiter...

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Meines Wissens nach nicht. Es gibt zwar Verfahren wie Best Fit und Worst Fit, aber in der Praxis ist First Fit schneller. Auch werden die Daten in einzelne Speicherbereiche gelegt.
Da wird bei First Fit nur drauf geachtet ob sie passen.
Nur alle paar Jubelsekunden Wird der Speicher dann aufgeräumt/die Speicherbereiche neu indexiert.
Jedenfalls meinem Wissen aus Info 3 nach.

Habe gerade auch nachgeschaut. Laut Skript wird dynamische Speicherverwaltung und First Fit meistens eingesetzt.
Darunter folgt der Satz, dass ältere Unix-Systeme damit arbeiten

Aber egal. Wir haben ein anderes Problem.
Beim Speicher bekommen wir ein Fragment/Ordner der irgendwo am besten reinpassen soll.
Hier haben wir die Ordner schon und schauen wie die am besten zusammenpassen, damit sie exact X MB Speicherplatz belegen.

Jo..hab ich mir auch überlegt. Deshalb die Frage an meinen TI Übungsleiter. Er hat noch nicht geantwortet. Wenn, dann schreib ichs hier rein.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ist das nicht ähnlich wie diese Rucksatz-Packen-Problem (KNAPSACK) ? Das war doch glaube ich eins von diesen Problemen, für die es keinen schnellen Algorithmus gibt.

Es ist DAS Problem

liefert nicht die beste, aber immerhin ne gute Lösung

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Also hab deine erste möglichkeit mal ausprobiert, aber irgendwie wenn ich das ganze umsetzte, funzt es nur halbwegs... er lässt einfach einträge aus
Teilweise gehts, aber nich so richtig.

Also beispielsweise hab ich hier 28 einträge, 2^28 wäre 784, also müsste es ja so aussehen:

Was macht denn FacIterative?
Falls die Funktion ne Fakultät berechnet, dann isses die falsche Wahl
Die Funktion, die Potenz zu berechnen heisst IntPower in der Unit Math.
Wenn Du alles in eine Schleife packst, dann sparst Du Dir viel Rechanzeit:

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Ich würde mir hier weniger Gedanken darüber machen, ob ich nicht vielleicht einen anderen Algorithmus finde, der das Gleiche effizienter erledigt, sondern mich entweder um alternativen Näherungen oder um Laufzeitersparnisse für den jetzigen Algorithmus kümmern.

Es macht zum Beispiel keinen großen Sinn jede Liste erstmal fertigzustellen und dann zu gucken ob die Größe überschritten wurde.
am besten ist, man zählt schön während dem Aufbau jeder Liste mit bei welchem Volumen man sich befindet und kann dann abbrechen, wenn man weiß, dass man in diesem Durchgang bereits über der maximalgröße ist. Ein weiterer Vorteil, den diese Veränderung hat ist folgender: Angenommen ich bin bei dieser Kombination angelangt:

00111010111010101111

Jetzt merke ich nach den ersten drei einsen, dass ich bereits die Maximalgröße überschritten habe, dann weiß ich auch, dass keine weitere zahl passen wird, bis ich nicht mindestens diese dritte eins in eine null verwandelt habe.

Subtrahiere jetzt also meinen derzeitigen Zähler von 00110000000000000000 und addiere die Differenz auf den Zähler.

Dazu muss ich dann natürlich mit while-Schleifen arbeiten.

Ich hoffe mal das ist kein Humbug den ich mir da grad ausgedacht hab.

Wenn ich nicht unbedingt immer das 100%ige Ergebnis haben muss, sondern eine Näherung es auch tut, kann man sich natürlich jede Menge alternative Algorithmen ausdenken, die andere Prioritäten haben, z.B. möglichst viele Pakete unterbringen, oder gemischte Größen etc.

Gruß
Jan

Nö isses nicht. Backtracking wird bei exponentiellen Algorithmen meist zur schadensbegrenzung eingesetzt. Man kann im durchschnittsfall ne Menge Zeit sparen, aber im Worstcase bleibt alles wies ist.

Backtracking ist ne gute idee. Sobald du eine Kombination gefunden hast, die nicht passt, dann passen alle anderen Kombinationen, die diese kombination beinhalten auch nicht.
Du könntest also die letzte Entscheidung Rückgängig machen, ein Flag setzen, dass das Bit xyz nicht wieder gesetzt werden darf, und was anderes ausprobieren. Wenn du rekursiv (erfolglos) zurück kommst, löscht du das Flag wieder, löscht ein anderes Bit, und setzt dessen Flag. Ich denke so könntest du dir ne Menge Zeit ersparen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com