Teilmengen berechnen

[Malcolm X]

Hallo,

folgende Klasse repräsentiert eine Kante in einem Graphen:

public class Kante 
{
	private int von;
	private int nach;
	
	public Kante(int von, int nach)
	{
		this.von = von;
		this.nach = nach;
	}
	
	public int getVon()
	{
		return this.von;
	}
	
	public int getNach()
	{
		return this.nach;
	}
}

Mal angenommen ich habe einen Graphen mit zwei Knoten, dann wären in diesem Graphen folgende Kanten möglich:

M = { (1,1), (1,2), (2,1), (2,2) }

Wie könnte denn ein Algorithmus aussehen der mir aus der Menge M sämtliche Teilmengen ermittelt?

Der Algorithmus müßte für das Beispiel folgendes Ergebnis liefern:

E =
{
{},
{(1,1)}, {(1,2)}, {(2,1)}, {(2,2)},
{(1,1)(1,2)}, {(1,1)(2,1)}, {(1,1)(2,2)}, {(1,2)(2,1)}, {(1,2)(2,2)}, {(2,1)(2,2)},
{(1,1)(1,2)(2,1)}, {(1,1)(1,2)(2,2)}, {(1,1)(2,1)(2,2)}, {(1,2)(2,1)(2,2)},
{(1,1)(1,2)(2,1)(2,2)}
}

 

[motschow]

vielleicht sowas...

 

[Malcolm X]

Könnt ihr mir sagen was ich an folgendem Code ändern muss damit er mit alle Teilmengen des Knoten arrays ausgibt?

import java.util.Vector;

/*
 *  der Code soll unabhängig von der Länge von knoten alle
 *  Teilmengen von knoten liefern.
 *  
 *  für das Beispiel wäre folgendes Ergebnis korrekt:
 *  
 *  { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1, 2, 3}  }  
 */

public class Teilmengen 
{
   private static int[] knoten = {1, 2, 3};
   private Vector<Vector> alleTeilmengen;
   private Vector<Kante> tempVector;
   
   public Teilmengen()
   {
       alleTeilmengen = new Vector<Vector>();
	   	
	   bildeLeereMenge();	   // {} geht soweit
	   bildeEinerMengen();     // {1}, {2}, {3} hier werden noch zuviele ausgegeben                  
	   bildeRestMengen();      // {1,2}, {1,3} {2,3}, {1, 2, 3} keine Ahnung wie das geht
   }
   
   public void bildeLeereMenge()
   {
   	   tempVector = new Vector<Kante>();
   	   alleTeilmengen.add(tempVector);
   }
   
   public void bildeEinerMengen()
   {  
       for(int i=0; i<knoten.length; i++)
   	   {
   	       for(int j=0; j<knoten.length; j++)
   		   {
   		       tempVector = new Vector<Kante>();
   			   tempVector.addElement(new Kante(i, j));
   			   alleTeilmengen.addElement(tempVector);
   		   }
   	    }
   }
   	
    public void bildeRestMengen()
    {
    	//???
    }
    
    public String toString()
    {
    	String ausgabe = "{";
    	
        for(int i=0; i<alleTeilmengen.size(); i++)
        {
            ausgabe += "\n\t{ ";
            
            for(int j=0; j<alleTeilmengen.elementAt(i).size(); j++)
            {
            	ausgabe += alleTeilmengen.elementAt(i).elementAt(j) + " ";
            }
        	
        	ausgabe += "}";
        }
        
        ausgabe += "\n}";
        
        return ausgabe;
    }
   
   public static void main(String[] args) 
   {
      Teilmengen teilmengen = new Teilmengen();  
      System.out.println(teilmengen);
   }
}

public class Kante 
{
	private int von;
	private int nach;
	
	public Kante(int von, int nach)
	{
		this.von = von;
		this.nach = nach;
	}
	
	public int getVon()
	{
		return this.von;
	}
	
	public int getNach()
	{
		return this.nach;
	}
	
	public String toString()
	{
		String ausgabe;
		ausgabe = "{" + von + "," + nach + "}";
		return ausgabe;
	}
}