Teilsummenproblem / welche Datenstruktur

[FelixN]

Hi!

folgendes Problem: Es geht um einen Algo der aus der Menge M mit n Elementen alle möglichen Teilmengen generiert.

Um den Algo an sich soll es nicht gehen, es geht darum, die erhaltenen Werte sinnvoll in Teilmengen abzuspeichern.

Jeder Treffer für ein jeweiliges X muss in ein eigenes Array bzw. Set. Also die Mengen separieren sich nach jedem Durchlauf der äußeren for-Schleife.

Schön wäre z.B eine ArrayList, die verschiedene HashSets abspeichert. Aber wie drücke ich aus: füge dem HashSet an dem ArrayListIndex[x] den Wert sum zu..da ich eine neues HashSet ja erst generieren muss, wenn if (binarStelle == 1) für ein neues x zutrifft.. bin ziemlich verzweifelt hier mein Code, der nicht klappt:

public static ArrayList<HashSet> teilmengenGenerieren1 (double [] sum) {

        ArrayList<HashSet> teilmengen = new ArrayList<HashSet>();
        
        for (int x = 0; x < (1L << sum.length); x++) {

            for (int i = 0; i < sum.length; i++) {
                long binaerStelle = (x >> i) & 1; //gibt Binärzahl von x an der Stelle i

                if (binaerStelle == 1) {
                    // adde sum[i] zur Menge an ArrayIndex X;
                    teilmengen.add(x, new HashSet());
                    teilmengen.get(x).add(sum[i]);
                    
                }
            }
        }
       return teilmengen;
    }

 

[Blender3D]

Es geht um einen Algo der aus der Menge M mit n Elementen alle möglichen Teilmengen generiert.

Meinst Du so etwas ?


Besser als ein Array für double wäre ebenfalls ein HashSet. Damit vermeidet man die Übergabe von doppelten Elementen.
[CODE lang="java" title="Potenzmenge"]import java.util.ArrayList;
import java.util.HashSet;

public class start {
public static void main(String[] args) {
double[] set = { 1, 2, 3, 4 };
ArrayList<HashSet<Double>> result = getPowerSet(set);
for (HashSet<Double> current : result) {
System.out.print("{ ");
for (Double i : current)
System.out.print(i + " ");
System.out.println("}");
}
}

public static ArrayList<HashSet<Double>> getPowerSet(double[] set) {
ArrayList<HashSet<Double>> result = new ArrayList<HashSet<Double>>();
boolean[] contains = new boolean[set.length];
subSets(set, contains, 0, result);
return result;
}

private static void subSets(double[] set, boolean[] contained, int start,
ArrayList<HashSet<Double>> result) {
if (start == contained.length) {
HashSet<Double> tmp = new HashSet<Double>();
for (int i = 0; i < contained.length; i++)
if (contained)
tmp.add(set);
result.add(tmp);
} else {
subSets(set, contained, start + 1, result);
contained[start] = true;
subSets(set, contained, start + 1, result);
contained[start] = false;
}
}
}[/CODE]

 

[FelixN]

Hi ! meine Aufgabenstellung war ein bisschen anders... daher kann ich das so nicht machen. Aber es hat mir trotzdem geholfen und bin dir super dankbar für deine Mühe, wirklich mega !!!!

Bin grade am schustern für meine Aufgabe.. hoffe es klappt. Wünsche dir ein schönes WE!