Schnittmenge von Boxen

[Mars3000]

Hallo zusammen,

ich habe folgendes Problem.
Stellen wir uns 5 Boxen vor, in denen verschiedene Kugeln(mit Id) enthalten sind:
Box1: 1, 2, 3
Box2: 1, 2, 3, 4
Box3: 2, 3, 5
Box4: 3, 4, 5
Box5: 2, 3

So, es geht nun darum auszugeben, gemeinesame Kugeln von verschiedenen Boxen auszugeben, also quasi die Schnittmenge. Der erste Schritt des Algorithmus wäre also:
Box1 & Box2: 1, 2, 3
Box1 & Box3: 2, 3
Box1 & Box4: 3
Box1 & Box5: 2, 3
Box2 & Box3: 2, 3
Box2 & Box4: 3, 4
usw.

Schritt zwei wäre dann, dass man die Schnittmenge von 3 Boxen herausfindet:
Box1 & Box2 & Box3: 2, 3
Box1 & Box2 & Box4: 3
Box1 & Box2 & Box5: 2, 3
Box2 & Box3 & Box4: 3

Der nächste Schritt die Schnittmenge von 4 Boxen und schließlich am Ende von 5 Boxen.

Also nochmal: Es geht darum, dass man N Boxen hat und zuerst 2-er-Gruppen, dann 3-er-Gruppen, ..., bis N-er-Gruppen testet und dafür bräuchte ich einen Algorithmus, auf den ich einfach nicht komme...

Ich bin dankbar für jede Hilfe

Um sich programmiertechnisch da mal was vorzustellen:

//Box1: 1, 2, 3
		Set<Integer> b1 = new HashSet<Integer>();
		b1.add(1);
		b1.add(2);
		b1.add(3);
        //Box2: 1, 2, 3, 4
		Set<Integer> b2 = new HashSet<Integer>();
		b2.add(1);
		b2.add(2);
		b2.add(3);
		b2.add(4);
		//Box3: 2, 3, 5
		Set<Integer> b3 = new HashSet<Integer>();
		b3.add(2);
		b3.add(3);
		b3.add(5);
		//Box4: 3, 4, 5
		Set<Integer> b4 = new HashSet<Integer>();
		b4.add(3);
		b4.add(4);
		b4.add(5);
		//Box5: 2, 3
		Set<Integer> b5 = new HashSet<Integer>();
		b5.add(2);
		b5.add(3);
		//Set von allen Boxen
		Set<Set<Integer>> allB = new HashSet<Set<Integer>>();
		allB.add(b1);
		allB.add(b2);
		allB.add(b3);
		allB.add(b4);
		allB.add(b5);

 

[SlaterB]

bisher hast du ja wirklich noch nicht viel, gar keine Idee zu gar nix?

ein Tipp:
mit einzelnen Variablen hast du es immer schwer, speichere sie in ein Array, Index 0-4, bzw. bis n-1
und dann kräftig Schleifen laufen lassen, also zumindest jeden Fall einzeln, etwa die 2er-Kombinationen, gehen per Schleife,
allgemein wäre Rekursion angesagt, aber das erst später

edit:
ok, mit allB ist das Array ja quasi schon umgesetzt, besser da doch auf Reihenfolge achten, also List statt Set

 

[Gast2]

Pseudocodemäßig so in etwa:

    private static Set<Integer> intersect(Set<Integer>... sets) {
    	// Liste mit allen nummern erstellen
    	Set<Integer> allNumbers = new HashSet<Integer>();
        // mit schleifen durch das array an Sets laufen und alle Zahlen adden
    	
    	// create the intersection
    	Set<Integer> intersection = new HashSet<Integer>();
        // alle Zahlen des oben erstellten Sets durchlaufen und prüfen ob die Zahl 
        // in allen übergebenen Sets enthalten ist, wenn ja, dann adden
    	
    	return intersection;
    }

 

[Mars3000]

Also erstmal Danke für die schnellen Antworten.

An etwas Rekursives hab ich auch schon gedacht, nur hab ich keinen Schimmer, wie ich das umsetzen sollte. Die Sache ist ja die:
Wenn man 2er-Paare vergleichen soll, dann geht das relativ easy. Man bildet schlicht zwei Listen mit allen Boxen und zwei Schleifen drüber und vergleich dann jeweils alle. Bei 3er-Paaren müssten es dann aber 3 Schleifen, bei 10er-Paare 10 Schleifen sein. Deswegen wäre da wohl nur was Rekursives hilfreich, oder ich hab eine Möglichkeit übersehen?

Also der Algorithmus ist Teil eines größeren Programms und da wird immer mit Sets gearbeitet. Deswegen wäre es schon vorteilhaft, wenn man das mit Sets hinbekommen würde - zur Not gingen Listen auch, aber da muss ich eben extra umwandeln...

Also 2er-Paare hätte ich jetzt so gemacht, wobei da auch noch das Problem ist, dass es box1 und box2 natürlich zweimal vergleicht...

//Die Speicherung des Ergebnisses ist nicht das Problem
		//Deswegen gib ich das Ergebnis hier nur aus
		
		Iterator<Set<Integer>> iteA = allB.iterator();
		
		
		while(iteA.hasNext()){
			Set<Integer> boxA = iteA.next();
			
			Iterator<Set<Integer>> iteI = allB.iterator();
			while(iteI.hasNext()){
				Set<Integer> boxB = iteI.next();
				if(boxA.equals(boxB))
					continue;
				Set<Integer> intersection = new HashSet<Integer>(boxB);
				
				intersection.retainAll(boxA);
				
				System.out.println("Die Schnittmenge von "+boxA+ " und "+boxB+" = "+intersection);
			}
			
		}

 

[Gast2]

Rekursiv kannst du da natürlich auch rangehen.
Du hast x Sets, jetzt "intersectest" du die listen x und x-1. Jetzt hast du eine Liste weniger. Mit denen machst du das gleiche, bis du nur noch eine Liste übrig hast.

Wenn du das nicht rekursiv machen willst dann schau dir meinen pseudocode an, da steht eigentlich schon alles drin.

 

[Mars3000]

Also entweder ich versteh deinen Pseudocode nicht oder du verstehst mein Problem nicht. Ich versteh deinen Pseudocode so, dass man die Schnittmenge aller Boxen bildet. Ich will die Schnittmenge von jeweils 2 Boxen, dann von jeweils 3 Boxen, dann von jeweils n Boxen.

Also ich meinem Kopf dreht sich alles. Aber ne Herangehensweise wäre doch, wenn man erst jeweils 2 Boxen miteinander vergleicht, die Schnittmengen speichere, um dann diese Schnittmenge(die dann 2 Boxen repräsentiert) mit einer weiteren Box auf eine Schnittmenge überprüfe, dann bekäme ich die Schnittmenge von jeweils 3 Boxen.
Hm, das verfolge ich jetzt mal

 

[Gast2]

Mit meiner Methode kannst du die Schnittmenge von x beliebigen Boxen bilden.
Übergibst du nur 2 Sets bestimmst du die Schnittmenge von den beiden Boxen. Übergibst du alle 5 Boxen dann bestimmst du die Schnittmenge aller 5 Boxen.

 

[Firephoenix]

Hi,
evtl liegt das Verständnisproblem auch an dem ... in dem Parameteraufruf.
Dieser funktioniert so, dass man die Methode mit beliebig vielen Parametern dieses Typs aufrufen kann und diese in einem Array abgelegt werden.
Daher eignet sich die Methode auch für mehrere Sets
Gruß

 

[Gast2]

Hier mal ausimplementiert:

	private static Set<Integer> intersect(Set<Integer>... sets) {
		// create a set with all numbers
		Set<Integer> allNumbers = new HashSet<Integer>();
		for (Set<Integer> s : sets) {
			allNumbers.addAll(s);
		}

		// create the intersection
		Set<Integer> intersection = new HashSet<Integer>();
		for (int number : allNumbers) {
			boolean valid = true;
			for (Set<Integer> s : sets) {
				if (!s.contains(number)) {
					valid = false;
					break;
				}
			}

			if (valid) {
				intersection.add(number);
			}
		}

		return intersection;
	}

 

[Landei]

Sets haben bereits eine Art intersection-Methode (ziemlich blöd [c]retainAll[/c] genannt), womit man das wesentlich einfacher implementieren könnte: Set #1 kopieren, und auf der Kopie nacheinander retainAll(Set #2), retainAll(Set #3) u.s.w. aufrufen.