N
New_Escaflowne
Gast
Hi.
ich habe folgendes Problem:
ich will eine Methode schreiben, die mir alle Möglichkeiten gibt, wie man x Gegenstände auf y Behälter aufteilt, d.h. bei vier Gegenständen (a,b,c,d) und zwei Behälter muss es 16 Möglichkeiten geben: von abcd/- über ab/cd, ad/bc, abd/c zu -/abcd (um nur ein paar zu nennen).
dazu habe ich mir folgendes ausgedacht:
ich habe eine Klasse Moeglichkeit, die aus einem Vector<Vector> (hier mal v genannt) und einigen anderen daten besteht, die aber für mein problem nicht von Relevanz sind. jeder Vector in v steht für einen Behälter und beinhaltet dementsprechen den Inhalt des Behälters.
in einem weiteren Vector speichere ich die einzelnen Möglichkeiten.
meine Methode sieht nun folgendermaßen aus (in pseudocode)
wie man sieht, ist es eine rekursive Methode. allerdings funktioniert sie nicht richtig, da ich, z.B. bei der Verteilung von vier Objekten (a,b,c,d) auf zwei Behälter nur 5 Möglichkeiten bekomme, die alle gleich aussehen, nämlich:
Behälter 1: a,b,c,d
Behälter 2: d,c,b,a
ich hoffe ihr könnt mir sagen, wo mein Fehler liegt. ich bedanke mich schonmal für die Hilfe.
mfg
New_Escaflowne
ich habe folgendes Problem:
ich will eine Methode schreiben, die mir alle Möglichkeiten gibt, wie man x Gegenstände auf y Behälter aufteilt, d.h. bei vier Gegenständen (a,b,c,d) und zwei Behälter muss es 16 Möglichkeiten geben: von abcd/- über ab/cd, ad/bc, abd/c zu -/abcd (um nur ein paar zu nennen).
dazu habe ich mir folgendes ausgedacht:
ich habe eine Klasse Moeglichkeit, die aus einem Vector<Vector> (hier mal v genannt) und einigen anderen daten besteht, die aber für mein problem nicht von Relevanz sind. jeder Vector in v steht für einen Behälter und beinhaltet dementsprechen den Inhalt des Behälters.
in einem weiteren Vector speichere ich die einzelnen Möglichkeiten.
meine Methode sieht nun folgendermaßen aus (in pseudocode)
Code:
methode() {
Vector unbearbeitet; //der Vector enthält alle Objekte
Vector<Vector> aktVerteilung; //ich speichere diesen Vector erst am Ende der Methode als Möglichkeit mit den anderen Werten
aktVerteilung wird mit so vielen leeren Vectoren gefüllt, wie es Behälter gibt;
tmp=unbearbeitet.get(0); //oberstes Objekt aus unbearbeitet
unbearbeitet.remove(0); //tmp wird aus unbearbeitet entfernt
for (int i=0; i<anzahlBehälter; i++) {
verteilungFinden(unbearbeitet, aktVerteilung, tmp, i);
}
... //rest ist nicht wichtig
}
verteilungFinden(Vector unbearbeitet, Vector<Vector> aktVerteilung, tmp, int pos) {
//unbearbeitet wie vorher, aktVerteilung=aktuelleVerteilung, tmp=aktuellesObjekt, pos=in welchen Behälter soll tmp
if (unbearbeitet.isEmpty()) { //Abbruchbedingung
aktVerteilung.get(pos).add(tmp); //tmp wird in den richtigen Behälter eingefügt
restliche Werde ermitteln, also die Verteilung bewerten;
aktVerteilung+Werte als Möglichkeit in den Vector mit allen Möglichkeiten einfügen;
} else {
aktVerteilung.get(pos).add(tmp);
t=unbearbeitet.get(0);
unbearbeitet.remove(0);
for (int i=0: i<anzahlBehälter; i++) {
verteilungFinden(unbearbeitet, aktVerteilung, t, i); //rekursiver Aufruf der Methode
}
}
}
wie man sieht, ist es eine rekursive Methode. allerdings funktioniert sie nicht richtig, da ich, z.B. bei der Verteilung von vier Objekten (a,b,c,d) auf zwei Behälter nur 5 Möglichkeiten bekomme, die alle gleich aussehen, nämlich:
Behälter 1: a,b,c,d
Behälter 2: d,c,b,a
ich hoffe ihr könnt mir sagen, wo mein Fehler liegt. ich bedanke mich schonmal für die Hilfe.
mfg
New_Escaflowne