Hi,
ich möchte zu einer gebenen Menge (z.B. int[] = {1,2,3}) die Permutationen (z.B. {3,2,1}, {2,1,3},...) und Kombinationen einer wählbaren Länge (z.B. Länge=2: {2,1}, {1,3}, {2,3}) rekursiv errechnen.
Bei den Permutationen klappt das auch ganz prima. Ich denke, dass die Kombinationen ähnlich zu lösen sind und nur "kleinere" Änderungen brauchen, aber ich bekomm es nicht hin. Ich bekomm viel zu viele Kombinationen ausgegeben, die eher den Permutationen entsprechen würden.
Die Strategie, die dahinter stecken soll ist, dass ich jedes Element einmal an die letzte Postion setze und danach rekursiv die Kombinationen der um das Elemente verkleinerten und der Länge-1 berechne...
Eine passende Testklasse:
ich möchte zu einer gebenen Menge (z.B. int[] = {1,2,3}) die Permutationen (z.B. {3,2,1}, {2,1,3},...) und Kombinationen einer wählbaren Länge (z.B. Länge=2: {2,1}, {1,3}, {2,3}) rekursiv errechnen.
Bei den Permutationen klappt das auch ganz prima. Ich denke, dass die Kombinationen ähnlich zu lösen sind und nur "kleinere" Änderungen brauchen, aber ich bekomm es nicht hin. Ich bekomm viel zu viele Kombinationen ausgegeben, die eher den Permutationen entsprechen würden.
Die Strategie, die dahinter stecken soll ist, dass ich jedes Element einmal an die letzte Postion setze und danach rekursiv die Kombinationen der um das Elemente verkleinerten und der Länge-1 berechne...
Code:
import java.util.Arrays;
public class Combinatorics {
protected int[] menge;
protected int laenge;
public void combine(int[] menge, int laenge) {
this.menge = menge;
this.laenge = laenge;
this.combineRecursive(laenge, 1);
}
protected void combineRecursive(int laenge, int maxElement) {
if(1 == laenge) {
printArray(laenge);
return;
}
for(int i=0; i< menge.length; i++) {
int mlen = menge.length;
// Wert nach hinten sichern
int tmp = menge[i];
menge[i] = menge[mlen-maxElement];
menge[mlen-maxElement] = tmp;
//
combineRecursive(laenge-1, maxElement+1);
// Rücktausch
tmp = menge[i];
menge[i] = menge[mlen-maxElement];
menge[mlen-maxElement] = tmp;
}
}
protected void printArray(int laenge) {
int[] out = new int[this.laenge];
for(int i=0; i<this.laenge; i++) {
out[i] = menge[menge.length-1-i];
}
System.out.println(Arrays.toString(out));
}
}
Eine passende Testklasse:
Code:
public class CombinatoricsTest {
public static void main(String[] args) {
int[] e = {1,2,3,4};
Combinatorics c = new Combinatorics();
// c.permute(e);
c.combine(e, 3);
}
}