Teilsummenproblem / welche Datenstruktur

FelixN

FelixN

Mitglied
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 :D hier mein Code, der nicht klappt:

Java:
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

Blender3D

Top Contributor
Es geht um einen Algo der aus der Menge M mit n Elementen alle möglichen Teilmengen generiert.
Meinst Du so etwas ?
Potenzmenge.JPG


Besser als ein Array für double wäre ebenfalls ein HashSet. Damit vermeidet man die Übergabe von doppelten Elementen.
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[i])
                    tmp.add(set[i]);
            result.add(tmp);
        } else {
            subSets(set, contained, start + 1, result);
            contained[start] = true;
            subSets(set, contained, start + 1, result);
            contained[start] = false;
        }
    }
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
P Welche Zeile in Tadople gibt einen compiler error? Java Basics - Anfänger-Themen 5
W Welche Komponente ist geeignet? Java Basics - Anfänger-Themen 1
A Welche Operation ist das? Java Basics - Anfänger-Themen 2
J Welche Java-Version installieren Java Basics - Anfänger-Themen 9
M Implementieren einer Datenstruktur, welche nur 5 Objekte speichert Java Basics - Anfänger-Themen 3
M Ausgabe einer Liste welche mehrere Stacks enthält Java Basics - Anfänger-Themen 3
K GUI Entwicklung - Welche Richtung passt für euch zum mobilen Zeitalter? Java Basics - Anfänger-Themen 4
T Datenbank | Welche am Sinnvollsten? Java Basics - Anfänger-Themen 5
S Welche Verteilung? Java Basics - Anfänger-Themen 1
L Welche Methode? Java Basics - Anfänger-Themen 7
O Methoden welche ich implementier Java Basics - Anfänger-Themen 11
A Wie erkennt die JVM welche class verwendet werden muss? Java Basics - Anfänger-Themen 3
M JDK installieren Welche Software bei XP? Java Basics - Anfänger-Themen 5
H Welche IDE zum Buch "Programmieren mit Java" von Reinhard Schiedermeier des Verlags Pearson Studium Java Basics - Anfänger-Themen 19
U Best Practice Fehleranalyse, welche Fehler macht Ihr beim Lernen bzw. auch später Java Basics - Anfänger-Themen 12
E jProgressbar, 6 Versuche, welche value angeben ? Java Basics - Anfänger-Themen 3
M Welche Entwicklungsumgebung? Java Basics - Anfänger-Themen 32
I Welche Schleife/Bedingung nehme ich her Java Basics - Anfänger-Themen 5
C Methoden Welche JSoup Methoden Und Parameter für diese HTML Tags Java Basics - Anfänger-Themen 4
K Erste Schritte Java lernen - Welche Bücher? Java Basics - Anfänger-Themen 1
P welche Komponente ist im Layout? Java Basics - Anfänger-Themen 2
TheMenox Methoden Bestimmung an welche Methode eine andere Methode ihren Wert weitergeben soll Java Basics - Anfänger-Themen 35
K Methoden mit den Namen accept. Welche Funktion haben diese? Java Basics - Anfänger-Themen 2
G Lambda Ausdruck: Welche Methode ist die Richtige? Java Basics - Anfänger-Themen 1
J Welche Methoden laufen im neuen thread ?? Java Basics - Anfänger-Themen 9
S Welche Datenstruktur ist die optimalste um Funktionen fuer bestimmte Wertebereiche abzurufen..? Java Basics - Anfänger-Themen 5
G Welche Java-Version auf meinem Rechner? Java Basics - Anfänger-Themen 2
Z Methoden Zugriff mit Klasse 3 auf Methode von Klasse 2 welche in Klasse 1 erzeugt wird Java Basics - Anfänger-Themen 6
A Klassen welche Klassen importiert Eclipse automatisch Java Basics - Anfänger-Themen 2
V welche Methode am besten sich für JPG einfügung in Java anzugewöhnen ? Java Basics - Anfänger-Themen 4
M Welche externen Bibliotheken sind in Java sehr zu empfehlen? Java Basics - Anfänger-Themen 4
I Grafische Benutzeroberflächen - welche Komponente nehme ich am besten? Java Basics - Anfänger-Themen 13
G Welche JAVA IDE? Java Basics - Anfänger-Themen 3
S Klassen Zugriff auf Attribute einer zweiten Klasse, welche durch dritte gesettet wurden? Java Basics - Anfänger-Themen 2
E wann welche Konstanten verwenden? Java Basics - Anfänger-Themen 7
K Welche Java Version ist die richtige Java Basics - Anfänger-Themen 3
V Welche Exceptions müssen importiert werden? Java Basics - Anfänger-Themen 3
A Design Pattern - Welche? Java Basics - Anfänger-Themen 33
C Datenbank - Welche Java Basics - Anfänger-Themen 5
S Welche Art von Liste? Java Basics - Anfänger-Themen 3
S Eigene Exception Schreiben und Welche Auslösen wie ? Java Basics - Anfänger-Themen 7
F Wenn genau welche Liste verwenden? Java Basics - Anfänger-Themen 6
T Welche Schleife? Java Basics - Anfänger-Themen 6
P Java Stream, wann welche Stream verwenden? Java Basics - Anfänger-Themen 3
S Collections Welche Collection ist am geeignetsten? Java Basics - Anfänger-Themen 3
S Input/Output Welche Möglichkeiten Eingabe von User abfragen Java Basics - Anfänger-Themen 5
P Swing - Welche Klasse für ausgeben von Ergebnissen? Java Basics - Anfänger-Themen 3
R Welche Datenstruktor für diese Liste? Java Basics - Anfänger-Themen 6
B Erste Schritte Welche Kenntnisse brauche ich für diese Programmidee? Java Basics - Anfänger-Themen 4
P Vererbung herausfinden welche Klasse was erbt Java Basics - Anfänger-Themen 3
K welche art von Liste für TableModell Java Basics - Anfänger-Themen 2
D Welche API für komplexe XML-Struktur? Java Basics - Anfänger-Themen 25
S welche Programmstruktur? Java Basics - Anfänger-Themen 8
M Welche Datenbank? Java Basics - Anfänger-Themen 5
B Welche Themengebiete benötige ich? Java Basics - Anfänger-Themen 7
StupidAttack Gson, welche Datenstruktur? Java Basics - Anfänger-Themen 4
S Welche Collection kann sich selber sortieren? Java Basics - Anfänger-Themen 8
H Welche Art der Ein/Ausgabe Java Basics - Anfänger-Themen 2
D Welche Datenstruktur für welche Problemstellung? Java Basics - Anfänger-Themen 10
U Welche(s) Framework(s) wären geeignet? Java Basics - Anfänger-Themen 8
StrikeTom Welche Dateitypen unterstützt JMF (Java Media Framework)? Java Basics - Anfänger-Themen 6
S Welche Collection? Java Basics - Anfänger-Themen 5
A Welche UML Software benutzt ihr / ist empfehlenswert? Java Basics - Anfänger-Themen 2
N Welche Datenstukturen und Methoden Java Basics - Anfänger-Themen 3
L Auswahl auf welche Art gespeichert werden soll Java Basics - Anfänger-Themen 6
B Welche Java-Installation ist aktiv? Java Basics - Anfänger-Themen 2
B Finden gemeinsamer Kanten: welche Datenstruktur ? Java Basics - Anfänger-Themen 9
S Welche möglichkeiten gibt es eine Zahl zu spiegeln? Java Basics - Anfänger-Themen 17
U Welche Seite für Anfänger Java Basics - Anfänger-Themen 11
K Welche Entwicklungsumgebung für Einsteiger? Java Basics - Anfänger-Themen 16
S Webapplikation welche alternative zu gwt? Java Basics - Anfänger-Themen 2
cowabunga1984 Unit-Testing - Welche Testfälle sind relevant? Java Basics - Anfänger-Themen 4
S Welche Methode in JFrame überschreiben? Java Basics - Anfänger-Themen 12
H Designfrage: Welche Liste? Java Basics - Anfänger-Themen 3
Z Welche IO-Klasse verwenden? Java Basics - Anfänger-Themen 2
G Welche Datenstruktur ( Sets / Maps)? Java Basics - Anfänger-Themen 10
M Der Java Schlüsselwort null; ?Welche Anweisung und Sinn? Java Basics - Anfänger-Themen 12
G Herausfinden, welche Componente als LETZTES focus hatte Java Basics - Anfänger-Themen 2
H Welche PDF Biblothek? Java Basics - Anfänger-Themen 6
G Variable welche in anderer Klasse liegt, verändern. Java Basics - Anfänger-Themen 2
G Frage:Welche Methodne kann man eine Zahl bzw. ein String Java Basics - Anfänger-Themen 3
U Welche Datenstruktur soll ich nehmen? Java Basics - Anfänger-Themen 11
K Welche Exception? Java Basics - Anfänger-Themen 6
G Welche Datenstruktur ist hier die sinnvolste Java Basics - Anfänger-Themen 6
G welche Teile der api sind wichtig? Java Basics - Anfänger-Themen 3
K Welche methoden gibt es in Java um Zahlen von der Java Basics - Anfänger-Themen 11
G welche Java-Technologie für JDBC geeignet Java Basics - Anfänger-Themen 6
G Welche Programmiersprache für ein Betriebssystem? Java Basics - Anfänger-Themen 12
D textdateien manipulieren, welche klasse? wie? Java Basics - Anfänger-Themen 8
S Welche Klasse erweitern? Java Basics - Anfänger-Themen 4
M Welche Schleife ist besser? Java Basics - Anfänger-Themen 6
G Welche Version zuerst? Java Basics - Anfänger-Themen 11
mwildam Welche Java-Version (SE oder EE)? Java Basics - Anfänger-Themen 9
M Welche Javaversion ist die Richtige? Java Basics - Anfänger-Themen 14
A Welche Collection? Java Basics - Anfänger-Themen 13
M welche Speichermethode verwenden? Java Basics - Anfänger-Themen 15
N Welche Klasse besitzt einen Standardkonstruktor ? Java Basics - Anfänger-Themen 30
S Welche Datenstruktur für Tabelle/DB? Java Basics - Anfänger-Themen 5
G Wofür com package? + Welche eclipse - Plug Ins? Java Basics - Anfänger-Themen 3
S Welche Sprache für ein Umfangreiches Webprojekt Java Basics - Anfänger-Themen 16

Ähnliche Java Themen

Anzeige

Neue Themen


Oben