Konstrukt um alle Paare und Tripel einer Punkte-Menge bilden

[Jay1980]

Servus,

wenn ich eine Menge von Elementen in einem Array habe, kann ich diese ja mit einer for-Schleife ablaufen.

Kennt jemand ein Tutorial, wo erklärt wird, wie ich ein Schleifenkonstrukt bauen muss, damit ich alle Paare und später alle Tripel erwische?

In meinem Fall habe ich eine Punktemenge aus Point-Objekten und will dann alle Punktepaare greifen und später alle Punktetripel.

Danke vorab.

 

[SlaterB]

was genau ist ein 'Element im Array' relativ zum Thema 'Punkte, Punktpaare, Tupel'?
ist ein Element ein Punkt?
wie ist denn die Paareigenschaft definiert?

gib ein Beispiel des Arrays und was genau in einer Aktion 'erwischt' werden soll

 

[Jay1980]

Ach,

vielleicht habe ich das etwas unverständlich formuliert, es ist aber ganz einfach:

Ich habe 5 Punkte. P1, P2, P3, P4, P5. Ein Paar ist P1 und P2, daraus bilde ich dann eine Strecke, das ist aber nicht wichtig, was mit dem Paar passiert. Wichtig ist, dass alle Kombinationen erwischt werden, also alle möglichen Paare der Elemente und dann später noch alle möglichen Tripel.

Paar 1: P1, P2
Paar 2: P1, P3
Paar 3: P1, P4
Paar 4: P1, P5
Paar 5: P2, P1
Paar 6: P2, P2
Paar 7: P2, P3

Das gleiche dann später mit den Dreierkombinationen, da die Reihenfolge unwichtig ist, wäre es als Verbesserung toll, wenn ich P1, P2 schon einmal als Paar hatte, dass dies das Konstrukt merkt und P2, P1 gar nicht mehr berechnet, sondern gleich das nächste Paar bildet.

 

[SlaterB]

for (i = 0 bis n) {
for (j =i+1 bis n) {
i und j
}
}

für Triple drei Schleifen,
per Rekursion könnte man beliebig viele Indexe vereinen, aber ungleich komplizierter, falls man darin nicht erfahren ist

 

[Jay1980]

Bist du so gut und machst das mal mit drei Schleifen - das ist nämlich genau das was ich nicht geschafft habe. Das mit dem Paar hat schon geklappt.

Das mit der Rekursion habe ich schon mit dem einfachen Beispiel der Fakultätsberechnung gemacht und ich habe schon vor, dass ich das Problem dann auch via Rekursion löse. Selbst kann ich das noch nicht, aber ich vermute das mir das Beispiel hier schon helfen würde. Die anderen Rekursionsbeispiele wie die 'Türme von Hanoi' sind noch schwer nachvollziehbar.

Wenn das zuviel ist, lass es bleiben, ich kann ja nicht einschätzen, ob du da viel denken musst, oder ob das für dich eine 3 Minuten-Aufgabe ist. Hast mir ohnehin schon oft weiter geholfen.

 

[SlaterB]

in 3 Min. könnte ich fast ein Programm schreiben, welches eine derartige Schleife als Quellcode produziert,
das ist wirklich nur die 2er-Variante weitergedacht, das kann sogar ein Computer

ich schreibe sie dir nicht hin, weil du selber darüber nachdenken sollst, sonst bringt das alles nix

 

[bygones]

ich schreibe sie dir nicht hin, weil du selber darüber nachdenken sollst, sonst bringt das alles nix

v.a. wenn man die 1xschleife und 2xschleife schreibt ist die 3x,4x etc ja nur die schlussfolgerung daraus ?!

 

[Jay1980]

Ich habe nahezu immer darüber nachgedacht, bevor ich hier eine Frage stelle. Über den iterativen Ansatz versteht sich, rekursiv habe ich es noch nicht geschafft. Meinen Versuch seht ihr unten, wie gesagt, ich scheitere an dem Versuch, alle Tripel zu bilden.

Zum Hintergrund: Erst werden alle Punktepaare gebildet, für jedes Punktepaar wird geschaut, ob alle Punkte der Punktemenge innerhalb oder ausserhalb des Umkreises zum aktuellen Punktepaar liegen. Hat man einen Kreis in dem alle Punkte liegen, dann wird sich dieser gemerkt. Dann wird das gleiche für die Tripel gemacht, mir gelingt es aber nicht alle Tripel zu bilden.

Alles habe ich in einer Methode, erste for-Schleife, greift sich alle Punkte, beginnt bei Stellplatz 1 und holt als Partner den Punkt einer Stelle weiter vorne. Stop ist beim Erreichen des letzten Punktes. Soweit so gut alle Paare abgeklopft.

Mit drei Punkten habe ich es noch nicht geschafft. Die erste Schleife geht durch alle Elemente, beginnt bei Stellplatz 2 und greift sich die beiden vorherigen als Partner, bis der letzte Stellplatz erreicht ist. Ich nehm ein Tripel, dann pruefe ich, aber wo und wie muss die for-Schleife aussehen, damit dann das nächste Tripel gebildet wird.

// bilde alle Punktepaare
		// Umsetzung: beginne an Stelle 1 und hole Voränger, so lange wie du < punkte.length bist
		for ( int i = 1; i < punkte.length; i++ )
		{
			Point tempPunktEins = new Point( punkte[i].x , punkte[i].y ); // Punkt Eins der Basis, int noetig, damit der Konstruktor klappt
			Point tempPunktZwei = new Point( punkte[i-1].x, punkte[i-1].y ); // Punkt Zwei der Vorgaenger von Punkt Eins im Array
			dbs += "Aktuelles Punktepaar: " + tempPunktEins.toString() + "; " + tempPunktZwei.toString() + "\n";
			
			// lasse die Kennzahlen fuers aktuelle Paar ermitteln
			Point tempMittelpunkt = berechneMittelpunktAusPunktepaar(tempPunktEins, tempPunktZwei);
			double tempRadius = berechneRadiusAusPunktepaar(tempPunktEins, tempPunktZwei);
			dbs += " +++ Kennzahlen fürs aktuelle Punktepaar: Mittelpunkt " + tempMittelpunkt.toString() + "; tempRadius: " + tempRadius + "\n";
			
			// teste alle Punkte ob diese im Kreis liegen
			for ( int l = 0; l < punkte.length; l++ )
			{
				// teste ob der aktuell getestete Punkt im Kreis liegt
				// dabei wird die Pruefung wenn der zu testende Punkt einer der Eckpunkte ist
				// gleich von der Funktion übernommen
				Point tempTestpunkt = new Point( punkte[l].x, punkte[l].y );
				boolean erg = testeObPunktAusserhalbVonKreisIst(tempMittelpunkt, tempRadius, tempTestpunkt, tempPunktEins, tempPunktZwei );
				dbs += "   +++ Testpunkt " + tempTestpunkt.toString() + " liegt ausserhalb des Kreises zum Punktepaar? " + erg + "\n";
				
				if ( erg == true ) // Punkt ist ausserhalb
				{
					// hole neues Punktepaar
					break; // Ausbruch aus der umgebenden for-Schleife
					
				}
				else
				{
					
					if ( l < punkte.length - 1 )
					{
						// wenn es einen weiteren Punkt gibt nimm diesen zum Lagentest
						// einfach nächsten Schleifendurchlauf starten, dann wird Testpunkt neu zugewiesen
						continue; 
					}
					else
					{
						// wenn es keinen nächsten Punkt zum Testen gibt, dann merk dir den Kreiskandidaten
						meldeKreisKandidat(tempMittelpunkt, tempRadius);
					}
				}
			}
		}
		
		// bilde alle Punktetripel
		for ( int j = 2; j < punkte.length; j++ )
		{
			Point tempPunktEins = new Point( punkte[j].x , punkte[j].y ); // Punkt Eins der Basis
			Point tempPunktZwei = new Point( punkte[j-1].x, punkte[j-1].y ); // Punkt Zwei der Vorgaenger von Punkt Eins im Array
			Point tempPunktDrei = new Point( punkte[j-2].x, punkte[j-2].y ); // Punkt Drei der Vorvorgaenger von Punkt Eins im Array
			dbs += "Aktuelles Punktetripel: " + tempPunktEins.toString() + "; " + tempPunktZwei.toString() + "; " + tempPunktDrei.toString() + ";\n";
		
			// lasse die Kennzahlen fuers aktuelle Tripel ermitteln
			Point tempMittelpunkt = berechneMittelpunktAusPunktetripel(tempPunktEins, tempPunktZwei, tempPunktDrei);
			double tempRadius = berechneRadiusAusPunktetripel(tempPunktEins, tempPunktZwei, tempPunktDrei, tempMittelpunkt);
			dbs += " +++ Kennzahlen fürs aktuelle Punktetripel: Mittelpunkt " + tempMittelpunkt.toString() + "; tempRadius: " + tempRadius + "\n";
			
			// teste alle Punkte ob diese im Kreis liegen
			for ( int l = 0; l < punkte.length; l++ )
			{
				// teste ob der aktuell getestete Punkt im Kreis liegt
				Point tempTestpunkt = new Point( punkte[l].x, punkte[l].y );
				boolean erg = testeObPunktAusserhalbVonKreisIst(tempMittelpunkt, tempRadius, tempTestpunkt, tempPunktEins, tempPunktZwei, tempPunktDrei );
				dbs += "   +++ Testpunkt " + tempTestpunkt.toString() + " liegt ausserhalb des Kreises zum Punktetripel? " + erg + "\n";
				
				if ( erg == true ) // Punkt ist ausserhalb
				{
					// hole neues Tripel
					break; // Schleifenausbruch
				}
				else
				{
					
					if ( l < punkte.length - 1 )
					{
						// wenn es einen weiteren Punkt gibt nimm diesen zum Lagentest
						// einfach nächsten Schleifendurchlauf starten, dann wird Testpunkt neu zugewiesen
						continue; 
					}
					else
					{
						// wenn es keinen nächsten Punkt zum Testen gibt, dann merk dir den Kreiskandidaten
						meldeKreisKandidat(tempMittelpunkt, tempRadius);
					}
				}
			}
		}
	}

 

[SlaterB]

nun ja, das hat dann zumindest mit den drei einfachen Schleifen nix mehr zu tun,

die 90 Zeilen Code zu verstehen ist mir bisschen viel,
hängt die Tupel/ Tripel-Eigenschaft von berechneMittelpunktAusPunktetripel() ab oder ist das beliebiger ZusatzCode drumherum?

immer noch und besonders jetzt wieder gilt:
Beispiele Beispiele Beispiele Beispiele Beispiele Beispiele Beispiele

nach dem Posting von 11:14 sollten einfach nur alle Punkte untereinander kombiniert werden,
das wären dann 5-10 Zeilen Code, keine 90

 

[Jay1980]

Ich habe mal das Problem aufs Einfachste beschränkt, vielleicht hilft dies einem, der auf den Thread stoesst und nach fertigen Schleifenbeispielen sucht, mir kostete es nun schon einige Zeit. Nun ja, dann baue ich derweil wieder an meiner Problemlösung.

@SlaterB
Die Paar/Tripel-Eigenschaft haengt nicht von der Pruefung ab, auch die for-Schleife die intern alle Punkte abklappert hat mit den Paaren und Tripeln nichts zu tun. Es ist nur so, dass wenn als Ergebnis rauskommt, dass ein getesteter Punkt ausserhalb des Kreises liegt, kann ein neues Tripel geholt werden, weil es schon reicht, dass ein Punkt ausserhalb liegt, damit ein möglicher Kreis als Kleinster Umschließender Kreis Kandidat durchfällt.

public class Punktekombos 
{
	int[] a;
	
	Punktekombos()
	{
		initialize();
	}
	
	public void initialize()
	{
		// Dummywerte anlegen
		a = new int[5];
		a[0] = 5;
		a[1] = 3;
		a[2] = 7;
		a[3] = 2;
		a[4] = 1;
		
		System.out.println("******** Zahlenkombos ******");
		System.out.println("... alle Zahlen einzeln ...");
		gibAlleZahlenAus();
		System.out.println();
		System.out.println("... alle Paare ...");
		gibAlleZahlenpaareAus();
		System.out.println();
		System.out.println("... alle Paare, aktueller Arraystellplatz exklusive ...");
		gibAlleZahlenpaareAusAktuellesElementExklusive();
		System.out.println();
		System.out.println("... alle Tripel ...");
		gibAlleZahlentripelAus();
		System.out.println();
		System.out.println("... alle Tripel, aktuelle Arraystellplaetze exklusive ...");
		gibAlleZahlentripelAusAktuelleElementeExklusive();
	}
	
	private void gibAlleZahlenAus()
	{
		for ( int i = 0; i < a.length; i++)
		{
			System.out.println(a[i]);
		}
	}
	
	private void gibAlleZahlenpaareAus()
	{
		for ( int i = 1; i < a.length; i++ )
		{
			for ( int j = 0; j < a.length; j++ )
			{
				System.out.println(a[i] + ", " + a[j]);
			}
		}
	}
	
	
	private void gibAlleZahlenpaareAusAktuellesElementExklusive()
	{
		for ( int i = 1; i < a.length; i++ )
		{
			for ( int j = 0; j < a.length; j++ )
			{
				if ( j == i )
				{
					continue;
				}
				System.out.println(a[i] + ", " + a[j]);
			}
		}
	}
	
	private void gibAlleZahlentripelAus()
	{
		for ( int i = 0; i < a.length; i++ )
		{
			for ( int j = 0; j < a.length; j++ )
			{
				for ( int k = 0; k < a.length; k++ )
				{
					System.out.println(a[i] +", " + a[j] + ", " + a[k] );
				}
			}
		}
	}
	
	private void gibAlleZahlentripelAusAktuelleElementeExklusive()
	{
		for ( int i = 0; i < a.length; i++ )
		{
			for ( int j = 0; j < a.length; j++ )
			{
				
				if ( j == i ) { continue; }
				
				for ( int k = 0; k < a.length; k++ )
				{
					if ( k == j ) { continue; }
					if ( k == i ) { continue; }
					System.out.println(a[i] +", " + a[j] + ", " + a[k] );
				}
			}
		}
	}
	
	public static void main(String[] args)
	{
		new Punktekombos();
	}
}

 

[JohannisderKaeufer]

	private void gibAlleZahlenpaareAus()
	{
		for ( int i = 0; i < a.length; i++ )//i mit 0 initialisieren
		{
			for ( int j = i; j < a.length; j++ )//j soll jeweils mit i starten
			{
				System.out.println(a[i] + ", " + a[j]);
			}
		}
	}
	
	
	
	
	private void gibAlleZahlentripelAus()
	{
		for ( int i = 0; i < a.length; i++ )
		{
			for ( int j = i; j < a.length; j++ )//j mit i starten
			{
				for ( int k = j; k < a.length; k++ )//k soll mit j starten
				{
					System.out.println(a[i] +", " + a[j] + ", " + a[k] );
				}
			}
		}
	}

Wenn du diese änderungen Berücksichtigst vermeidest du das du die Kombination 1,2 und 2,1 bekommst. Eine Kombination 1,1 bzw. 2,2 bleibt allerdings möglich.

Wenn du das auch ausschließen möchtest

	private void gibAlleZahlenpaareAus()
	{
		for ( int i = 0; i < a.length; i++ )//i mit 0 initialisieren
		{
			for ( int j = i+1; j < a.length; j++ )//j soll jeweils mit i + 1  starten
			{
				System.out.println(a[i] + ", " + a[j]);
			}
		}
	}
	
	
	
	
	private void gibAlleZahlentripelAus()
	{
		for ( int i = 0; i < a.length; i++ )
		{
			for ( int j = i; j < a.length; j++ )//j mit i+1 starten
			{
				for ( int k = j; k < a.length; k++ )//k soll mit j+1 starten
				{
					System.out.println(a[i] +", " + a[j] + ", " + a[k] );
				}
			}
		}
	}

 

[JohannisderKaeufer]

Ein Rekursiver ansatz

public void doIt(int sovielNoch,int start){
if(sovielNoch<=0){
  System.out.println();
}else{
  for(int i = start;i<a.length;i++){
    System.out.print(a[i]);
    doIt(sovielNoch--, i);
//doIt(sovielNoch--,i+1); falls P1,P1 unerwünscht ist
  }
}
}

in main
doIt(2,0); //Paare
doIt(3,0;//Triple

 

[0x7F800000]

Ein Rekursiver ansatz...

Ja, schön ist der Ansatz! Schön kurz. Mir ist allerdings etwa ein Jahr lang nicht eingefallen, wie man das denn so machen soll, dass es nicht nur zeugs auf Bildschirm schreibt, sondern die Teilmengen in irgendeiner verwertbaren Form liefert. Jetzt ist es mir eingefallen:

import java.util.*;
import java.util.concurrent.*;

public class _ {
	
	public static <T> Iterable<Collection<T>> getFixedSizeSubsets(Collection<T> c,final int k){
		final ArrayList<T> randomAccessList=new ArrayList<T>(c);
		
		return new Iterable<Collection<T>>(){
			@Override
			public Iterator<Collection<T>> iterator() {
				return new Iterator<Collection<T>>(){
					private final Collection<T> POISON=new ArrayList<T>();
					
					private Collection<T> next;
					private BlockingQueue<Collection<T>> queue=new ArrayBlockingQueue<Collection<T>>(1024<<4);
					{
						new Thread(){
							private void rec(Collection<T> alreadyChosen, int stillToChoose, int start){
								if(stillToChoose==0){
									try{
										queue.put(alreadyChosen);
									}catch(InterruptedException e){}
								}else{
									for(int i=start; i<randomAccessList.size(); i++){
										Collection<T> a=new LinkedList<T>(alreadyChosen);
										a.add(randomAccessList.get(i));
										rec(a,stillToChoose-1,i+1);
									}
								}
							}
							
							@Override
							public void run(){
								rec(new LinkedList<T>(),k,0);
								try{
									queue.put(POISON);
								}catch(InterruptedException e){}
							}
						}.start();
						findNext();
					}
					
					private void findNext(){
						try{
							next=queue.take();
							if(next==POISON){
								next=null;
							}
						}catch(InterruptedException e){
							next=null;
						}
					}
					
					@Override
					public boolean hasNext() {
						return next!=null;
					}

					@Override
					public Collection<T> next() {
						Collection<T> result=next; 
						findNext();
						return result;
					}

					@Override
					public void remove() {
						throw new UnsupportedOperationException("This Iterable represents a set " +
																"defined by some properties, " +
																"it is not a manipulable data structure");
					}
				};
			}	
		};
	}
	
	public static void main(String...  args){
		Collection<String> c=new LinkedList<String>();
		for(int i=1; i<10; i++){
			c.add(""+i);
		}
		for(Collection<?> e:getFixedSizeSubsets(c,5)){
			System.out.println(e);
		}
	}
}

Ist immer noch etwa 5x langsamer als Marco13's halb-iterative index-weiterschalt-variante. ;( (http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html) [bzw. ich hab's jetzt nicht an Marco13's implementierung gemessen, sondern an meiner, die aber recht analog aussieht, vielleicht ist Marco13's Originalprogramm nochmal schneller]

Die Idee bei dieser Implementierung besteht darin, dass man die Rekursion praktisch genauso übernimmt, wie JohannisderKaeufer das vorgeschlagen hat, allerdings lässt man sie im separaten Thread laufen, und schmeißt die Ergebnisse nicht auf die Konsole, sondern in eine Warteschlange, sodass sie vom Iterator abgeholt werden können. Wenn der Thread fertig ist, wird der Konsument vergiftet.

Imho ist der Algo in der Form etwas lesbarer und leichter nachzuvollziehen (bezieht sich jetzt ausschließlich auf die Methode "rec", nicht auf den ganzen kram drumherum, denn dort steckt die Logik, der Rest ist Verpackung). Aber es ist nunmal 5x lahmer... :autsch: