# Kombinationen einer Menge rekursiv berechnen



## Loep (29. Nov 2007)

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...


```
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:

```
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);
	}

}
```


----------



## SlaterB (29. Nov 2007)

also ich bekomme da Exceptions, gar keine Ausgaben..,

verwende

if (0 == laenge)
        {
            printArray();
und 
combineRecursive(laenge - 1, maxElement + 1);
dann läuft das einigermaßen,

Problem ist nun noch, dass du Doppelte in Form von
[2,3]
+
[3,2]
bekommst,
wenn du das vermeiden willst, dann wäre eine Möglichkeit,
in der i-Schleife zu prüfen, ob das aktuelle Elemente kleiner ist als alle bereits fest stehenden (am Ende das Arrays),
wenn ja, dann gehts weiter, sonst für dieses i abbrechen


----------



## Loep (29. Nov 2007)

Ich hatte im Editor hier noch was geändert, was wohl die Exception verursachte, hab den Code oben editiert, so läuft er bei mir.

if(laenge == 1) scheint aber besser zu laufen als 
if(laenge == 0), da bei deinem Vorschlag gleiche Kombinationen mehrfach ausgegeben werden. Bei 1 scheinen alle nur einmal zu kommen.

Bei meinem Versuch über if(menge_ < menge[menge.lenght-1] continue; doppelte zu entfernen, kommen viel zu wenig Kombinationen herum._


----------



## SlaterB (29. Nov 2007)

> Bei 1 scheinen alle nur einmal zu kommen. 

wenn nur einmal dann wärst du ja fertig, paar doppelte sind auch,
ob alle Kombis drankommen kann ich auf die Schnelle nicht genau sagen, bei 0 auf jeden Fall

vorallem versagt die 1 bei kleineren Mengen, wenn du etwa alle einelementigen suchst,
die 0 findet alle, aber eben doppelt, wahrscheinlich mehrfach doppelt, 

> Bei meinem Versuch [..] kommen viel zu wenig Kombinationen herum.

mit "Eingabe x, Ausgabe y" wären solche Fragen viel leichter zu klären..,

ich jedenfalls habe mal 
if (maxElement > 1 && menge_ >= menge[mlen - maxElement + 1])
            {
                continue;
            }
benutzt und bekomme bei

        int[] e = {1, 2, 3, 4};
        Combinatorics c = new Combinatorics();
        // c.permute(e);
        c.combine(e, 3);

(sowie 0 statt 1) die Ausgabe

[3, 2, 1]
[4, 2, 1]
[4, 3, 1]
[4, 3, 2]

sind doch alle die du willst, oder?_


----------



## Loep (29. Nov 2007)

Ok, klappt auf den ersten Blick prima...
Das mit dem ==0 muss ich mir nochmal ansehen.
Die if() continue hatte ich bei all meinen Versuchen falsch herum verglichen.
Danke!

PS: Hatte die angegebene Eingabemenge genommen, aber natürlich wäre ne Ausgabe dabei angebracht gewesen.


----------



## Gast (1. Dez 2007)

könnte einer von euch evtl nochmal den fertigen code posten?

ich hab nen ähnliches porblem zu bewältigen, konnte den code auch ganz gut umschreiben, dass er mir genügt (bin nich so fit in java, deshalb kann ichs alleine gar nich), allerdings bekomm ich die if abfrage

if (maxElement > 1 && menge_ >= menge[mlen - maxElement + 1])
{
continue;
} 

nicht da reingebastelt und habe daher die doppelten ausgaben...

wär nett, danke_


----------



## Loep (1. Dez 2007)

Bist du zufällig Student und hast bei Kuchen Info-Vorlesung? 
Wenn ja, in welcher Übungsgruppe bist du? Können ja nicht 2 Teams die selbe Lösung abgeben.


----------



## Gast (1. Dez 2007)

ne.... bin kein Student... bin schüler

muss das genau auch nirgends abgeben.... ist nur ein teilproblem meiner aufgabe

aber wenn dus abgeben musst und nicht willst das es sonst jemand sieht kann ich es verstehen


----------



## Gast (2. Dez 2007)

kann man in dieser Klasse auch die Permutationen dieser Menge implementieren?


----------



## Guest (2. Dez 2007)

An welcher Uni bist n du?


----------



## Loep (2. Dez 2007)

In Combinatorics ist die Berechnung der Permutationen und Kombinationen beliebiger Länge implementiert.
Wenn ich drank denke, kann ich ab morgen Mittag den Code posten.

Uni Münster


----------



## Loep (3. Dez 2007)

Hi,

hier mal die Klasse Combinatorics, die Permutationen und Kombinationen rekursiv errechnet.
Perfektioniert ist sie sicherlich noch nicht, aber für die Anforderungen reichts (z.B. Fehleingaben werden gar nicht behandelt)


```
import java.util.Arrays;

public class Combinatorics {
	protected int[] menge;
	protected int originalLaenge;

	public void permute(int[] menge) {
		// Element-Array global zugänglich machen
		this.menge = menge;
		// Rekursion aufrufen
		this.permuteRecursive(menge.length);
	}

	protected void permuteRecursive(int n) {
		// wenn nur ein Element, gesamtes Feld ausgeben
		if(n==1) {
			System.out.println(Arrays.toString(menge));
		} else {
			// sonst jedes Element einmal "festhalten" und um 1 kleineres Feld behandeln
			for(int i=0; i<n; i++) {
				// "festzustellendes" Element nach hinten tauschen
				int tmp = menge[n-1];
				menge[n-1] = menge[i];
				menge[i] = tmp;
				// Feld mit Länge-1 bearbeiten, dadurch wird "festes" Element ignoriert
				this.permuteRecursive(n-1);
				// in Ursprungszustand zurück tauschen
				tmp = menge[n-1];
				menge[n-1] = menge[i];
				menge[i] = tmp;
			}
		}
	}

	public void combine(int minElement, int maxElement, int laenge) {
		int anzahl = Math.abs(maxElement-minElement)+1;
		int[] m = new int[anzahl];
		for(int i=0; i<anzahl; i++) {
			m[i] = minElement+i;
		}
		this.combine(m, laenge);
	}

	public void combine(int[] menge, int laenge) {
		this.menge = menge;
		this.originalLaenge = laenge;
		this.combineRecursive(laenge, 1);
	}

	protected void combineRecursive(int laenge, int maxElement) {
		if(0 == laenge) {
			printArray(this.originalLaenge);
			return;
		}
		int mlen = menge.length;
		// jedes Element einmal als x wählen
		for(int i=0; i< mlen; i++) {
			// Wert nach hinten sichern
			int tmp = menge[i];
			// Elemente, die in anderer Reihenfolge schon da waren, ignorieren
			if (maxElement > 1 && menge[i] >= menge[mlen - maxElement + 1]) {
				continue;
			}
			menge[i] = menge[mlen-maxElement];
			menge[mlen-maxElement] = tmp;
			// Menge ohne aktuellen Element bearbeiten und Kombinationen dafür mit Länge-1 suchen
			combineRecursive(laenge-1, maxElement+1);
			// Rücktausch
			tmp = menge[i];
			menge[i] = menge[mlen-maxElement];
			menge[mlen-maxElement] = tmp;
		}
	}

	protected void printArray(int laenge) {
		// hintere Felder entsprechen der Kombination, da dorthin getauscht wurde
		int[] out = new int[laenge];
		for(int i=0; i<laenge; i++) {
			out[i] = menge[menge.length-1-i];
		}
		System.out.println(Arrays.toString(out));
	}

}
```

Eine passende Testklasse dazu:

```
import java.util.Arrays;

public class CombinatoricsTest {

	public static void main(String[] args) {
		int[] e = {1,2,3,4};
		int laenge = 3;
//		int minElement = 2, maxElement =4;
		Combinatorics c = new Combinatorics();
		System.out.println("Permutationen: (Menge=" + Arrays.toString(e) + ")");
		c.permute(e);
		System.out.println("Kombinationen: (Menge=" + Arrays.toString(e) + ", Länge=" + laenge + ")");
		c.combine(e, laenge);
//		c.combine(minElement, maxElement, laenge);
	}

}
```

Und die Ausgabe, die die Testklasse erzeugt:

```
Permutationen: (Menge=[1, 2, 3, 4])
[2, 3, 4, 1]
[3, 2, 4, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[4, 3, 1, 2]
[3, 4, 1, 2]
[3, 1, 4, 2]
[1, 3, 4, 2]
[4, 1, 3, 2]
[1, 4, 3, 2]
[2, 4, 1, 3]
[4, 2, 1, 3]
[4, 1, 2, 3]
[1, 4, 2, 3]
[2, 1, 4, 3]
[1, 2, 4, 3]
[2, 3, 1, 4]
[3, 2, 1, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
Kombinationen: (Menge=[1, 2, 3, 4], Länge=3)
[3, 2, 1]
[4, 2, 1]
[4, 3, 1]
[4, 3, 2]
```

(c) Kuchen-Übungsgruppe Uhsener Nr. 9


----------

