Häufigkeit von Spielzeug

[Mackz]

Diese Programmieraufgabe wurde von einem User vorgeschlagen, der gerne anonym bleiben möchte.

Hallo HaBo,

ich hab eine neue Programmieraufgabe für euch, die mit ein wenig Anstrengung für die meisten von euch denk ich kein Problem ist.


Gegeben ist eine Tabelle mit folgendem Inhalt:

Sie soll darstellen welche Kinder welches Spielzeug besitzen.

spielzeug		          kinder
___________________________________

lego			stefan
playstation		stefan
rc-car			stefan

lego			robert
playsation		robert
computer		         robert

lego			marcus
playstation		marcus

rc-car			michael
computer		         michael
lego			michael

Ihr könnt für die jeweiligen Kinder bzw. für das Spielzeug natürlich eine ID verwenden oder den Inhalt völlig austauschen.

Wichtig dabei ist, dass die beiden Spalten eine n:n Verbindung haben. Das heißt, ein Spielzeug kann mehreren Kindern gehören und ein Kind kann mehr als eines haben.

Im obigen Beispiel ist "lego" das Spielzeug das am häufigsten verwendet wird. Das wäre ja eigentlich relativ leicht rauszufinden.

Der gesuchte Algorithmus soll nun aber die beiden Spielzeuge finden, die am häufigsten zusammen bei einem Kind Verwendung finden.

Das wäre bei unserem Beispiel "lego" und "playstation". Wird nämlich beides von drei Kindern verwendet.

Die Quelle für den Algorithmus soll nun aber natürlich erweiterbar sein.

 

[CDW]

Da niemand antwortet und ich mich unbedingt wieder mit dem neumodischen Zeug auseinander setzen wollte:

Spoiler: ein bisschen Java

Aufruf aus dem Hauptprogramm:

	public static void getInput(RelManagment db)
	{
		db.newBinRelation("toystat","Spielzeug","Kind");
		db.addBinRelation("toystat","lego","stefan");
		...
		db.addBinRelation("toystat","computer","michael");		
	}
	
	public static void main(String[] args) 
	{		
		RelManagment db=new RelManagment();
		getInput(db);
		
		System.out.println("Zwei beliebteste Spielzeuge, die bei einem Kind vorhanden sind:");
		Object[] result=db.selectHighestRelations("toystat","Spielzeug");		
		for (int i=0;i<result.length;i++)
			System.out.println(result[i]);

der Algorithmus selbst:
Hauptziel war, eine bessere Best/AverageCase Laufzeit zu erhalten, als m*n?/2 , die man sonst mit einer Tabelle zustande bekommt.

Man stelle sich das ganze als eine Ansammlung von Mengen vor:
Menge Kind enthält {PC,Lego,PS}

Kind2={Fahrrad,Lego,rc-car}
usw.

Natürlich geht es auch andersherum:

playstation={ robert,marcus,stefan}
lego={robert,marcus,stefan,michael}
rc-car={stefan,michael}
computer={ robert,michael}

Gesucht sind nun zwei Mengen, die am meisten gemeinsame Elemente haben - deren
Schnittmenge (alle Elemente, die sowohl in Menge1 wie auch Menge2 vorkommen) also die größte Mächtigkeit hat.

Wenn man die gegebenen Mengen nun nach Mächtigkeit sortiert:

lego={robert,marcus,stefan,michael}
playstation={ robert,marcus,stefan}
rc-car={stefan,michael}
computer={ robert,michael}

kann man sie der Reihe nach durchgehen:
(starte mit der ersten Menge)
1.betrachte die aktuelle Menge und gehe der Reihe nach die anderen Mengen durch, ermittele dabei jeweils mit der aktuellen Menge gemeinsame Elemente (also den Schnitt).
Ist die Kardinalität (Mächtigkeit) der bisher größten ermittelten Schnittmenge >=der Mächtigkeit der nächsten zu betrachtenden Menge, brich die Betrachtung ab (Grund: da diese Mengen schon nach ihre Mächtigkeit sortiert sind, macht es keinen Sinn, sie alle durchzugehen, da sie dann weniger/gleichviele Elemente enthalten und wir somit auch keinen größeren Durchschnitt als den aktuellen finden werden).

2. gehe von der aktuellen zu der nächsten Menge. Hat diese weniger oder gleich viele Elemente, wie bereits im Schritt 1. gefundener Schnitt , sind wir fertig. Ansonsten gehe zu 1.


Bsp: start: lego-Menge:

1.lego+playstation haben 3 Elemente gemeinsam, die nächste Menge wäre
rc-car, diese hat aber nur 2 Elemente , also weiter mit Schritt 2
2.gehe zu Playstation, diese hat 3 Elemente. Wir haben breits einen Schnitt mit 3 Elementen - besser wird es nicht, daher sind wir fertig.

    private Set getHighestRelationTo(ListIterator listIter, Set set)
    {
    	Set interSet=new Set(),tmpSet;	
    	
    	while (listIter.hasNext())
    	  {  	  	
    	  	tmpSet=(Set)listIter.next();
    	  	if (interSet.getCardinality()>=tmpSet.getCardinality()) break;   // sind die restlichen 
    	  	//Mengen überhaupt groß genug,um mehr Übereinstimmungen, als aktuell vorhanden, zu liefern?			
			
			tmpSet=tmpSet.getIntersections(set);  //durchschnitt bilden
    	  	if (tmpSet.getCardinality()>interSet.getCardinality()) {interSet=tmpSet;}    	  	 	  	    	  	  
    	  }
    	return interSet;
    }
   
  public Object[] selectHighestRelations(String name,String dimName)    
  {		
    ArrayList queue;		
    ListIterator listIter;
    Set interSet=new Set(),tmpSet;
		
    BinRelation relation=(BinRelation)relations.get(name);
    if (relation==null) return new Object[0];
		
    queue=relation.getDimension(dimName);
    if (queue==null) return new Object[0];
		
    listIter=queue.listIterator();
    while (listIter.hasNext())
    {
       tmpSet=(Set)listIter.next();
       //ist die nächste (und damit auch nachfolgende) Menge(n) kleiner,
       //als der aktuelle Durchschnitt,können sie gar nicht mehr Übereinstimmungen enthalten		   
      if (interSet.getCardinality()>=tmpSet.getCardinality()) break; 
		   
      tmpSet=this.getHighestRelationTo(queue.listIterator(listIter.nextIndex()),tmpSet);		
        if (tmpSet.getCardinality()>interSet.getCardinality()) interSet=tmpSet;
    }
    return interSet.getReferences().toArray();
  }

Wobei: das Ermitteln, ob ein Element auch in einer anderen Menge vorhanden ist, funktioniert in konstanter Zeit (es werden letzendlich HashSets->HashTables genutzt).
Dabei wird immer die kleineste Menge ausgewählt und überprüft, ob deren Elemente in der anderen Menge vorhanden sind. Aufwand der Schnittmengenbildung ist also = der Anzahl der Elemente in der kleineren Menge.

Spoiler: Output:

Zwei beliebteste Spielzeuge, die bei einem Kind vorhanden sind:
lego
playstation

Zwei Kinder, deren Spielzeugsammlung sich am meisten ähnelt:
stefan
robert
Gesamtdarstellung (Spielzeug): 

lego: robert,marcus,stefan,michael,
playstation: robert,marcus,stefan,
rc-car: stefan,michael,
computer: robert,michael,

Gesamtdarstellung (Kinder):

stefan: lego,rc-car,playstation,
robert: computer,lego,playstation,
michael: computer,lego,rc-car,
marcus: lego,playstation,

Im Anhang ist das komplette Programm (start mit java -jar RelStuff.jar, Quellcode ist auch da drin), welches eventuell etwas größer erscheint (weil ich unbedingt das BackEnd allgemeiner halten wollte ). Das Ganze lässt sich allerdings auch mit weniger Code umsetzen, wenn man nur explizit auf die Aufgabenstellung eingeht.