kombination von elementen in einer liste

[noisebreath]

Hi ,

ich bräuchte einen algorithmus der 1 liste beliebiger länge nimmt und ihre elemente in allen möglichkeiten kombiniert.

Beispiel:

liste = {1,3,4,5}

ergebnisliste = {(1+3),(1+4),(1+5),(3+4),(3+5),(4+5),(1+3+4),(1+3+5),(1+4+5),(1+3+4+5)}


solch einen Algorithmus gibt es doch bestimmt schon oder? weiss nur nicht nach was ich googlen soll. Wäre sehr dankbar, wenn man mir da weiterhelfen könnte.

lg
noise

 

[SlaterB]

kann es auch ein Set statt einer Liste sein?
potenzmenge java - Google-Suche

 

[noisebreath]

	public void potenzmenge_erstellen (Set neue_Liste, Set zu_verarbeitende_Elemente)
	{
		Iterator it1 = neue_Liste.iterator();
		Iterator it2 = zu_verarbeitende_Elemente.iterator();
		Object erstes_Element_der_zu_verarbeitenden_Elemente;
		if (it2.hasNext())
		{
			erstes_Element_der_zu_verarbeitenden_Elemente = it2.next();
		}
		else
		{
			Set b = new Set();
			neue_Liste.add(b); //Die leere Menge hinzufügen
			return;
		}
		while(it1.hasNext())
		{
			Object aktuelles_Item_neue_Liste = it1.next();
			Set neu_hinzuzufuegen = new Set(aktuelles_Item_neue_Liste); //neues Set mit dem aktuellen Item als Grundlage
			neu_hinzuzufuegen.add(erstes_Element_der_zu_verarbeitenden_Elemente);
			neue_Liste.add(neu_hinzuzufuegen);
		}
		neue_Liste.add(erstes_Element_der_zu_verarbeitenden_Elemente);
		zu_verarbeitende_Elemente.remove(erstes_Element_der_zu_verarbeitenden_Elemente);
		if (it2.hasNext())
		{
			potenzmenge_erstellen(neue_Liste,zu_verarbeitende_Elemente);
		}
		else
		{
			neue_Liste.add(new Set()); //Die leere Menge hinzufügen (ist doppelt drin, quasi aus Sicherheitsgründen, um eventuelle Fehlerquellen zu minimieren)
			return;
		}
	}

meinst wahrscheinlich sowas.

Ich hab aber einach Vector of Files und will einfach für alle kombinationen von files eine Operation x ausführen.
sozusagen

ergebnis = {(file1 x file2),(file1 x file3),....(file1 x file2 x file3 x file4 x file5)}

nebenbei kann er bei mir set nicht instantiieren.

 

[SlaterB]

Set ist ein Interface, HashSet wäre eine denkbare Klasse,
Grundlagen zu Collections sind hier natürlich essentiell

ob nun File oder andere Art von Objekte dürfte doch egal sein

 

[bygones]

das sollte doch weiterhelfen
http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html

 

[noisebreath]

also ich hab mir jetzt meinen eigenen code dazu geschrieben, aber er schmeißt mir einen fehler den ich so nicht verstehe:

public class MergedFilesHolder {

	
	private File[] mergedFiles;
	
	int [] list = {1,2,3,4,5};
	
	MergeItem [] vec=new MergeItem[100];
	
	
	public void addMergedFile(){
		for (int i=0 ; i < list.length; ++i){
			if (i == 0){
				for(int j= 0; j < list.length-1; ++j){
					for (int p=j+1; p < list.length; ++p){
						MergeItem temp = new MergeItem();
						temp.sum=list[p]+list[j];
						temp.highest_index = p;
						temp.length = i+2;
						for(int h = 0; h<vec.length;++h){
							if(vec[h]==null){
								vec[h]=temp;
								break;
							}
						}
					}
				}
			}else{
				int index1 = 0;
				while(vec[index1].length < i+1)
					++index1;
				
				int index2 = index1;
				System.out.println(vec[index2].length);
				System.out.println(i+1);
				while(vec[index2].length == i+1){ //error
					for(int l = vec[index2].highest_index+1;l < list.length;++l){
						MergeItem temp = new MergeItem();
						temp.sum = vec[index2].sum + list[l];
						temp.highest_index = l;
						temp.length = i+2;
						for(int h = 0; h<vec.length;++h){
							if(vec[h]!=null){
								vec[h]=temp;
								break;
							}
						}
					}
				
				++index2;
				}
			}
		}
		for(int i= 0;i<vec.length;++i){
			System.out.println(vec[i]);
		}
	}
}

ausgabe:
2
2
Exception in thread "main" java.lang.NullPointerException
at de.unituebingen.pinweb.ExtractionBroker.Merge.util.MergedFilesHolder.addMergedFile(MergedFilesHolder.java:41)
at testclasses.test.main(test.java:14)

keine ahnung was da nicht läuft..

 

[SlaterB]

hier etwas ausführlicher:

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
        new MergedFilesHolder().addMergedFile();
    }


}


class MergedFilesHolder
{


    private File[] mergedFiles;

    int[] list =
        {1, 2, 3, 4, 5};

    MergeItem[] vec = new MergeItem[100];


    public void addMergedFile()
    {
        for (int i = 0; i < list.length; ++i)
        {
            if (i == 0)
            {
                for (int j = 0; j < list.length - 1; ++j)
                {
                    for (int p = j + 1; p < list.length; ++p)
                    {
                        MergeItem temp = new MergeItem();
                        temp.sum = list[p] + list[j];
                        temp.highest_index = p;
                        temp.length = i + 2;
                        for (int h = 0; h < vec.length; ++h)
                        {
                            if (vec[h] == null)
                            {
                                System.out.println("fill position h: " + h);
                                vec[h] = temp;
                                break;
                            }
                        }
                    }
                }
            }
            else
            {
                int index1 = 0;
                while (vec[index1].length < i + 1)
                    ++index1;

                int index2 = index1;
                System.out.println(vec[index2].length);
                System.out.println(i + 1);
                while (vec[index2].length == i + 1)
                { // error
                    for (int l = vec[index2].highest_index + 1; l < list.length; ++l)
                    {
                        MergeItem temp = new MergeItem();
                        temp.sum = vec[index2].sum + list[l];
                        temp.highest_index = l;
                        temp.length = i + 2;
                        for (int h = 0; h < vec.length; ++h)
                        {
                            if (vec[h] != null)
                            {
                                vec[h] = temp;
                                break;
                            }
                        }
                    }

                    ++index2;
                    System.out.println("index2: " + index2);
                }
            }
        }
        for (int i = 0; i < vec.length; ++i)
        {
            System.out.println(vec[i]);
        }
    }
}


class MergeItem
{

    public int sum;
    public int highest_index;
    public int length;
}

fill position h: 0
fill position h: 1
fill position h: 2
fill position h: 3
fill position h: 4
fill position h: 5
fill position h: 6
fill position h: 7
fill position h: 8
fill position h: 9
2
2
index2: 1
index2: 2
index2: 3
index2: 4
index2: 5
index2: 6
index2: 7
index2: 8
index2: 9
index2: 10
Exception in thread "main" java.lang.NullPointerException
	at test.MergedFilesHolder.addMergedFile(Test.java:65)
	at test.Test.main(Test.java:11)

was immer das Programm auch machen soll, das Array wird bis Index 9 befüllt,
die while-Schleife kommt zum Index 10 -> kein Objekt mehr da

 

[noisebreath]

k mom