Kombinationen einer Menge rekursiv berechnen

Status
Nicht offen für weitere Antworten.

Loep

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

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

}
 
S

SlaterB

Gast
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

Aktives Mitglied
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.
 
S

SlaterB

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

Aktives Mitglied
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.
 
G

Gast

Gast
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

Aktives Mitglied
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.
 
G

Gast

Gast
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
 
G

Gast

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

Loep

Aktives Mitglied
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

Aktives Mitglied
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)

Code:
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:
Code:
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:
Code:
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
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Summe aus Kombinationen /permutationen einer Liste mit einer Obergrenze Java Basics - Anfänger-Themen 10
D Rekursiv Kombinationen ausgeben klappt nur bei einer Wiederholung Java Basics - Anfänger-Themen 4
K Kombinationen der Elemente einer ArrayList Java Basics - Anfänger-Themen 4
S Rekursive Kombinationen Java Basics - Anfänger-Themen 6
R0m1lly Kombinationen aus int array rekursiv Java Basics - Anfänger-Themen 2
C alle möglichen Kombinationen zweier Ziffern auf drei / vier / und 'n" Stellen Java Basics - Anfänger-Themen 11
C Array in allen Kombinationen ausfüllen Java Basics - Anfänger-Themen 17
D Alle möglichen Kombinationen in einem Array ausgeben Java Basics - Anfänger-Themen 2
L Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich Java Basics - Anfänger-Themen 6
Phash Kombinationen erzeugen Java Basics - Anfänger-Themen 4
L Kombinationen nur mit if/while erstellen Java Basics - Anfänger-Themen 2
B Kombinationen 3-dim Array Java Basics - Anfänger-Themen 5
D Kombinationen Quadratisches Array Java Basics - Anfänger-Themen 11
F 4 STrings in allen Kombinationen miteinander kombinieren Java Basics - Anfänger-Themen 2
F Kombinationen mit 3 Würfeln Java Basics - Anfänger-Themen 6
-horn- Alle Kombinationen von Zahlenreihe ohne Doppelungen Java Basics - Anfänger-Themen 6
C Alle Möglichen Kombinationen eines Arrays Java Basics - Anfänger-Themen 5
F Knifflig: Kombinationen von Zeiträumen Java Basics - Anfänger-Themen 3
M Kombinationen von Objekten bilden Java Basics - Anfänger-Themen 5
M Ausgabe einer ArrayList ensteht nur als Hashcode, nicht als Objekt Java Basics - Anfänger-Themen 16
D 2 ArrayListen gleich sortieren bzw. eine Liste anhand einer anderen Sortieren Java Basics - Anfänger-Themen 6
ixChronos Letzten 4 Ziffern einer großen Zahl ausgeben Java Basics - Anfänger-Themen 3
P Objekt einer Methode eines anderen Objektes übergeben Java Basics - Anfänger-Themen 5
L Variablenwerte aus einer Methode übergeben Java Basics - Anfänger-Themen 2
E Arrays in einer ArrayList miteinander vergleichen Java Basics - Anfänger-Themen 12
Simon16 Java ArrayListe von einer Klasse sortieren Java Basics - Anfänger-Themen 2
Shadowrunner Variablen Gibt es eine Möglichkeit die Ziffern/Stellen einer Zahl fest zu legen? Java Basics - Anfänger-Themen 3
D remove Object von einer Liste von Obejcts Java Basics - Anfänger-Themen 3
FunkyPhil94 Wert in einer Lambda Funktion erhöhen Java Basics - Anfänger-Themen 3
T Aufruf der Methode einer Oberklasse, wenn sie in der Unterklasse überschrieben ist. Polymorphie. Java Basics - Anfänger-Themen 2
B Kommunikation mit Seriellen Schnittstellen + Integration einer lib Java Basics - Anfänger-Themen 1
A Daten aus einer HashMap aus einer DB speichern und mit neuen Werten vergleichen Java Basics - Anfänger-Themen 8
P Welches SDK für das erstellen einer ausführbaren Datei? Java Basics - Anfänger-Themen 4
D Länge einer Liste aufrufen. Java Basics - Anfänger-Themen 19
J Klassen Instanzen einer Klasse in einer anderen unabhängigen Klasse nutzen Java Basics - Anfänger-Themen 4
B Alle Strings bis zu einer Maimallänge aufzählen, die Bedingung erfüllen Java Basics - Anfänger-Themen 13
marcelnedza Finde meinen Fehler in einer Methode nicht, Java Karol Java Basics - Anfänger-Themen 15
Soranix Erste Schritte Struktur als Anfänger // Von einer Klasse auf ein Objekt einer anderen Klasse zugreifen. Java Basics - Anfänger-Themen 6
MoxMorris Wie macht man String[] = String[] aus einer anderer Methode? Java Basics - Anfänger-Themen 18
T Fibonacci mit einer Hilfsmethode berechnen Java Basics - Anfänger-Themen 10
S Hilfe zu einer Aufgabe Java Basics - Anfänger-Themen 5
M Radius von einer ellipse bestimmen Java Basics - Anfänger-Themen 7
Say Fehlenden Code finden in einer while-Schleife? Java Basics - Anfänger-Themen 11
M Zufallszahl generieren mit einer linken und rechten Grenze Java Basics - Anfänger-Themen 3
N Was Passiert mit dem Namen einer Variable, wenn man diese einer Liste Hinzufügt Java Basics - Anfänger-Themen 16
_user_q Wie eine Methode/Funktion aus einer Klasse mit Constructor aufrufen? Java Basics - Anfänger-Themen 20
W String einer Textdatei in einzelne Stringobjekte pro Zeile aufteilen Java Basics - Anfänger-Themen 14
W Objekte einer ArrayList in txt-datei schreiben mit Paths? Java Basics - Anfänger-Themen 2
S Best Practice Fragen zu Projektstruktur einer Datenbank-Abfrage-App (MVC) Java Basics - Anfänger-Themen 13
T Variable von Objekten in einer Methode überprüfen Java Basics - Anfänger-Themen 26
nelsonmandela Problem bei Ausgabe einer Switch - Case Funktion Java Basics - Anfänger-Themen 5
S Textausgabe in einer For-Schleife Java Basics - Anfänger-Themen 12
M Spezifischen Wert einer Zeile aus .txt Datei entnehmen Java Basics - Anfänger-Themen 15
B Popups mit Klicksabfangen zumAusfüllen einer .ods Datei Java Basics - Anfänger-Themen 0
M RandomAccessFile int und String gleichzeitig in einer Datei Java Basics - Anfänger-Themen 49
E Suchfunktion in einer Liste Java Basics - Anfänger-Themen 39
T ungeordnete Werte-Paare in einer Liste Java Basics - Anfänger-Themen 7
FireHorses Einen Command erst nach einer Chateingabe aktivieren Java Basics - Anfänger-Themen 1
frager2345 Singleton-Muster Java ->Nur eine Instanz einer Klasse erzeugen können Java Basics - Anfänger-Themen 45
F wie kann ich die Position des letzten Vokals innerhalb einer Zeichenkette ermitteln? Java Basics - Anfänger-Themen 5
H Kapselung protected aber in einer Kindklasse nicht zugänglich Java Basics - Anfänger-Themen 5
R Methoden Werte einer ArrayList als Parameter übergeben. Java Basics - Anfänger-Themen 4
B Den Dateipfad einer Java Datei durch Code in Selbiger finden? Java Basics - Anfänger-Themen 10
LilliCherry Array in einer Zeile ausgeben Java Basics - Anfänger-Themen 6
B Attribute eines Objekts einer Klasse durch statische Methode einer 2. Klasse ändern? Java Basics - Anfänger-Themen 32
L Dauerhaftes Speichern einer Eingabe bei einer ArrayList Java Basics - Anfänger-Themen 26
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
G Position einer unbekannten 3-stelligen-Zahl in einem String finden Java Basics - Anfänger-Themen 15
stormyark Fehler beim überschreiben einer Variable Java Basics - Anfänger-Themen 1
H Kompliziertes Sortieren einer ArrayList mit Objekten(Sortieren nach X und Y) Java Basics - Anfänger-Themen 11
T Permanentes speichern von Objekten in einer ArrayList Java Basics - Anfänger-Themen 6
Saiko Zeilen einer Datei einlesen Java Basics - Anfänger-Themen 3
H Erste Schritte Nach einer Zahl n soll n Mal der String untereinander ausgegeben werden Java Basics - Anfänger-Themen 3
G zwei Instanzen einer Klasse Java Basics - Anfänger-Themen 29
sserio Prüfziffer einer ISBN Nummer herrausfinden. Java Basics - Anfänger-Themen 14
J Benennung einer mir unbekannten Java - Ausdrucksweise Java Basics - Anfänger-Themen 5
LFB In einer For-Schleife alles in einer Zeile ausgeben Java Basics - Anfänger-Themen 14
sserio Wie kann man nach einer Klasse fragen? Java Basics - Anfänger-Themen 12
berserkerdq2 Wann soll ich den Stream schließen, wenn ich das in einer Methode habe? Java Basics - Anfänger-Themen 8
berserkerdq2 Wie gebe ich den Pfad zu einer Datei an, die in einem Ordner in Eclipse ist? Java Basics - Anfänger-Themen 1
M Variable in einer Schleife initialisieren Java Basics - Anfänger-Themen 46
D EinMalEins mithilfe einer for-Schleife und Array Java Basics - Anfänger-Themen 1
J int innerhalb einer Datei ändern Java Basics - Anfänger-Themen 1
D Hilfe bei einer Aufgabe mit for-Schleife Java Basics - Anfänger-Themen 6
Neuling47 Ich zerbreche mit den kopf an einer Aufgabe Java Basics - Anfänger-Themen 61
H Mit setter-Methode JLabel in einer andern Klasse ändern. Java Basics - Anfänger-Themen 40
J Zelleninhalt einer Jtable löschen Java Basics - Anfänger-Themen 2
Robert_Klaus Hamster java Simulation Hilfe bei einer Aufgabe Java Basics - Anfänger-Themen 5
stormyark 4 Bit in einer for-schleife funktioniert nicht Java Basics - Anfänger-Themen 3
F Werte in einer Arraylist Zählen Java Basics - Anfänger-Themen 2
M ArrayList mit einer Schleife befüllen Java Basics - Anfänger-Themen 2
A Ein Array bearbeiten und in einer anderen Methode nutzen Java Basics - Anfänger-Themen 6
A Ergebnis einer Methode bei einer anderen verwenden Java Basics - Anfänger-Themen 13
I Interface von einer EJB Klasse, um Code zu reduzieren Java Basics - Anfänger-Themen 1
M Interface als Parameter einer Klasse Java Basics - Anfänger-Themen 8
I Liste von Infos von einer eigenen Annotation in Liste speichern Java Basics - Anfänger-Themen 0
M Wie kann ich den Index i von einer LinkedList überprüfen? Java Basics - Anfänger-Themen 36
M Wie kann die Implementation einer Methode den Wert eines Attributs vermindern? Java Basics - Anfänger-Themen 3
M Wie verknüpfe ich eine Bedingung mit einer Methode ohne if-Verzweigung & Bedingungsoperator? Java Basics - Anfänger-Themen 2
P Doppelte werte in einer Liste zählen Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Neue Themen


Oben