Algoritmus für 3er-Paare von n Zahlen

[Pfeiffy]

Hallo,
irgendwie stehe ich gerade auf dem Schlauch und bekomme es einfach nicht hin: folgendes Problem:
ich habe n Zahlen 1,2....n, aus diesen sollen alle Kombinationen von 3e-Paaren ermittelt werden, jedes 3er-Paar soll jedoch nur einmal vorkommen, und jede Zahl nu 1 mal im Paar Reihenfolge ist egal
Beispiel: Zahlen: 1,2,3,4
Erg:
1,2,3
1,2,4
1,3,4
2,3,4
Wie kann ich das in Java programmieren?

Gruß und Dank
Pfeiffy

 

[SlaterB]

du brauchst drei Schleifen oder eine Rekursion, die beliebig viele Schleifen zulässt,

in der ersten Schleife wählst du als erstes die 1,
in der zweiten Schleife wählst du als erstes die nächst höhere Zahl, die 2,
in der dritten Schleife wählst du als erstes die nächst höhere Zahl, die 3,
dann hast du die erste Kombination gefunden (1,2,3),

nun wird munter hochgezählt, wie man es bei ineinander geschachtelten Schleifen so kennt natürlich erstmal in der inneren Schleife,
in der dritten Schleife kommt nach 3 die 4 -> 1,2,4 gefunden,

da 4 der Maximalwert ist ist die dritte Schleife vorerst beendet, die zweite Schleife wieder dran, statt 2 dort nun 3 und die dritte Schleife muss wieder arbeiten (die jetzt nicht auch 3 wählen darf, sondern bei 4 anfangen muss)

so bekommst du nach und nach alle erlaubten Kombinationen,
wichtig ist, dass jede Schleife den aktuellen Wert der vorherigen berücksichtigt,

mit Rekursion ist das recht elegant zu lösen, für den Anfang solltest du aber verschachtelte Schleifen verwenden,
fange z.B. zunächst mit zwei Schleifen an und einer Ausgabe
1,2
1,3
1,4
2,3
2,4
3,4

 

[Gast]

mit Rekursion ist das recht elegant zu lösen

ich bin der meinung, dass man rekursionen vermeiden soll, die führen recht schnell zu speicher proglemen...

 

[Marco13]

Eine erwas zu pauschale Aussage. Man kann viele Probleme sehr elegant mit Rekursion lösen, bei denen eine iterative Lösung ein ziemlicher K(r)ampf wäre :autsch: Insbesondere, wenn die Laufzeit exponentiell mit der Rekursionstiefe steigt, dürfte der Spiecher das geringste Problem sein :wink:

 

[Maeher]

Man kann viele Probleme sehr elegant mit Rekursion lösen, bei denen eine iterative Lösung ein ziemlicher K(r)ampf wäre

Ich hatte mal eine Variante geschrieben, die ohne Rekursion aus einer beliebigen Kombination die jeweils nächste geliefert hat, bin gerade auf der Suche, war aber glaube ich in C++.
Die Rechenzeit war mit Abstand das größte Problem, solange man nicht auf die Idee kommt alle Ergebnisse speichern zu wollen. Der Vorteil bei dieser Lösung ist, dass man die Funktion von überall her aufrufen kann, während man bei einer Rekursion die Verwendung der Ergebniskombinationen irgendwie fest einbauen muss.
(Editiert)
Edit: hab's gefunden und Java draus gemacht, ist aber nicht wirklich schön...

 

[0x7F800000]

Also, ich hätte hier eine ziemlich allgemeine Lösung, die für eine endliche Menge alle Teilmengen der festgelegten Größe liefert:

import java.util.*;

public class FiniteSubsets {
	
	/** getSubsets
	 * 
	 * @param <T>	any Type 
	 * @param S		a finite Set with elements of Type T
	 * @param n		size of subsets
	 * @return		set of subsets of S that have size n
	 */
	
	public static <T> Set<Set<T>> getSubsets(Set<T> s, int n){
		
		Set<Set<T>> resultingSetOfSubsets=new HashSet<Set<T>>();
		
		if(n<=0){	
			//the set of subsets with size=0 contains only the empty subset
			//the result IS NOT EMPTY, it's a set that contains the empty set!
			resultingSetOfSubsets.add(new HashSet<T>());
		}else{		
			//return all nonempty subsets
			for(T e:s){
				//take the element e out of the finite Set s and calculate all (n-1)-Subsets of s\e
				Set<T> s_e=new HashSet<T>(s); s_e.remove(e);
				Set<Set<T>> subsetsOfS_e=getSubsets(s_e, n-1);
				
				//now reunite each subset of s\e with {e}
				//and add the result into the set of subsets of s
				for(Set<T> subsetOfS_e : subsetsOfS_e){
					subsetOfS_e.add(e);				//reunite with {e}
					resultingSetOfSubsets.add(subsetOfS_e);	//add to the set of subsets of s
				}
			}
		}
		
		return resultingSetOfSubsets;
	}
	
	// TEST
	public static void main(String[] args){
		//array int[] is autoboxed to Integer[], transformed into List and added to HashSet...
		//looks a little bit complicated^^
		HashSet<Integer> s=new HashSet<Integer>(Arrays.asList(new Integer[]{1,2,3,4,5}));
		
		//now get all subsets of s with size=3
		Set<Set<Integer>> subsets=getSubsets(s,3);
		
		//print the result
		System.out.println("Set\t\t="+s);
		System.out.println("Set of Subsets\t="+subsets);
		
	}
}

auf dieses konkrete Beispiel bezogen liefert es zum beispiel für die menge {1,2,3,4,5} alle teilmengen mit Betrag 3:

Set =[1, 2, 3, 4, 5]
Set of Subsets =[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [2, 3, 4], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

Das sind auch genau (5 über 3) stück...

Es ist rekursiv und in der Tat wohl recht speicherfressend und auch nicht allzuschnell. (Wobei bei solchen kombinatorischen Geschichten die benötigte Zeit und Speicherverbrauch allgemein recht schnell ansteigt)
Dafür ist das imho die denkbar einfachste Lösung.

Speziell für int[]-Arrays würde das ganze wohl noch ein bisschen einfacher aussehen, da ohne generics, aber das kann man sich aus diesem Beispiel bei bedarf schnell basteln, wenn das prinzip klar ist...

 

[Maeher]

Hier meine Variante aus dem alten C-Code (nicht schön aber funktioniert, nur der Startwert 0,1,2,... wird nicht ausgegeben):
Man kann durch Aufruf von getNext() ohne nennenswerten Speicherverbrauch immer wieder neue (Integer-)Kombinationen erzeugen (auch viele Mio).

public class SortGen {

    private int st; //Anzahl Stellen
    private int moegl; //Anzahl Möglichkeiten pro Stelle
    private int[] akt; //aktuelles Ergebnisarray
    private boolean[] istm; //istm[a] gibt an ob a eine Möglichkeit ist oder bereits verwendet ist

    /**
     * 
     * @param st Stellen
     * @param vals Anzahl der möglichen Werte
     */
    SortGen(int st, int vals) {
        this.st = st;
        moegl = vals;
        istm = new boolean[moegl];
        akt = new int[st];

        for (int i = 0; i < st; i++) {
            akt[i] = i;
        }
    }

    private void istMoegl() {
        int i;
        for (i = 0; i < moegl; i++) { //Alle auf möglich setzen
            istm[i] = true;
        }
        for (i = 0; i < akt.length; i++) {
            istm[akt[i]] = false; //Für in akt vorkommende Werte auf false setzen
        }
    }
    //Nächste Reihenfolge errechnen
    private boolean next() {
        int i, j, k, l; //Schleifeniteratoren
        istMoegl();

        for (i = 0; i < st; i++) { //Für jede Stelle (von hinten)
            istm[akt[st - 1 - i]] = true; //Zu bearbeitende Stelle wieder möglich
            for (j = akt[st - 1 - i] + 1; j < moegl; j++) { //Vom Wert der i-ten Stelle von hinten (+1) bis zum max. mögl. Wert
                if (istm[j]) { //Wenn Wert noch möglich
                    akt[st - 1 - i] = j; //An der i-ten Stelle von hinten Wert einsetzen
                    istm[j] = false; //Wert j an anderen Stellen nicht mehr möglich
                    for (k = st - i; k < st; k++) { //Folgende auffüllen mit kleinstmöglichen Werten (k=Position)
                        for (l = 0; l < moegl; l++) { //mögliche Werte durchprobieren
                            if (istm[l]) {
                                akt[k] = l;
                                istm[l] = false;
                                break;
                            }
                        }
                    }
                    return true;
                }
            }
        }
        akt = null;
        return false;
    }

    /**Startwert wird nie ausgegeben; nach dem letzten Wert wird <code>null</code> zurückgegeben.
     * 
     * @return
     */
    public int[] getNext() {
        next();
        return akt;
    }

    //Testmethode
    public static void main(String[] args) {
        SortGen sG = new SortGen(5, 6);

        long time = System.nanoTime();
            for (int i = 0; i < 500; i++) {
                int[] r = sG.getNext().clone();
                System.out.println(r[0] + " " + r[1] + " " + r[2] + " " + r[3] + " " + r[4]);
            }
        System.out.println(System.nanoTime() - time);
    }
}

Bitte entschuldigt das Kauderwelsch und den hässlichen Abbruch

Edit: main() Testmethode

 

[0x7F800000]

könntest du auch schnell noch eine beispiel-main methode in den code einfügen, irgendwie ist mir nicht ganz klar wie man das anwendet ???:L
"3er-Paar" ist aber ein echt interessantes Wort fällt mir grad auf... 3-Tupel heisst es eigentlich^^

 

[Maeher]

könntest du auch schnell noch eine beispiel-main methode in den code einfügen, irgendwie ist mir nicht ganz klar wie man das anwendet ???

Falls du mich meinst: erledigt (s.o.). Die Zeitmessung misst so nach meiner Erfahrung allerdings hauptsächlich die System.out's.
Vielleicht sollte ich mich mal um eine Anständige Dokumentation kümmern ???:L

 

[diggaa1984]

heisst das dann nicht Tripel?

 

[0x7F800000]

@diggaa1984:

heisst das dann nicht Tripel?

das mit n-Tupeln ist imho irgendwie allgemeiner, da muss man sich nciht jedes mal überlegen wie es denn eigentlich heisst^^

@Maeher:
dein code liefert zusätzlich alle denkbaren Permutationen, dem OP war aber die Reihenfolge egal. Aber schön zu wissen, dass man auch die Untergruppen der Symmetrischen Gruppe auf diese weise schnell berechnen kann (da müsste man dann aber noch ein wenig was ergänzen)

 

[Pfeiffy]

Hallo,
also erstmal vielen Dank für die Lösungen, das mit dem Speicherfressen muss ich dann erst mal sehen, bei meiner Rechnung werden schon sehr viele Zahlenmengen eingegeben, ich muss dann sehen, wie es sich verhällt, aber mein Dienstrechner kann einiges ab.

Gruß und Dank
Pfeiffy

 

[Maeher]

@Maeher:
dein code liefert zusätzlich alle denkbaren Permutationen, dem OP war aber die Reihenfolge egal.

Hupps , hab wohl gestern die ersten Posts nicht sauber gelesen.
Da ist meine Lösung natürlich nicht wirklich zweckmäßig.