Abrufen eines Powersets eines Satzes in Java

86

Das Powerset von {1, 2, 3}ist:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Angenommen, ich habe eine Setin Java:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

Wie schreibe ich die Funktion getPowerset mit der bestmöglichen Reihenfolge der Komplexität? (Ich denke, es könnte O (2 ^ n) sein.)

Manuel Araoz
quelle
7
Angenommen, Sie haben eine Reihe von Konfigurationen - beispielsweise "A", "B" und "C" -, mit denen ein Modell parametrisiert werden kann, und Sie möchten sehen, welche Teilmenge das beste Ergebnis liefert - z. B. nur "A. ". Eine mögliche Lösung wäre, jedes Mitglied des Powersets zu testen.
João Silva
7
Es ist eine Google-Interviewfrage für Softwareentwickler. Es ist ein erfundenes Problem, Ihre geistige Beweglichkeit zu testen.
Eric Leschinski
Dies ist eine vernünftige Frage. Um beispielsweise die Bewertungsfunktion für Cribbage zu implementieren, müssen Sie testen, ob sich ein Element des Powersets zu 15 addiert.
John Henckel

Antworten:

100

Ja, das ist es O(2^n)tatsächlich, da Sie 2^nmögliche Kombinationen generieren müssen . Hier ist eine funktionierende Implementierung, die Generika und Sets verwendet:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  

Und ein Test anhand Ihrer Beispieleingabe:

 Set<Integer> mySet = new HashSet<Integer>();
 mySet.add(1);
 mySet.add(2);
 mySet.add(3);
 for (Set<Integer> s : SetUtils.powerSet(mySet)) {
     System.out.println(s);
 }
João Silva
quelle
Wäre es schneller, Iterator anstelle von list zu verwenden? Beispiel: Setze <T> rest = new HashSet <T> (originalSet); Iterator <T> i = rest.iterator (); T head = i.next (); ich entferne(); ?
Dimath
1
@CosminVacaroiu ... was könnte es sonst noch tun?
user253751
3
Bist du sicher, dass es so ist O(2^n)? Das ist die Anzahl der Sätze im Leistungssatz, aber jeder Satz muss im Speicher erstellt werden, was mindestens proportional zur Satzgröße dauert. Laut Wolfram Alpha ist es in O(n * 2^n): Wolfram Alpha Query
Fabian
1
Würde dies funktionieren, selbst wenn die Größe des Sets in der Größenordnung von 10 ^ 5 liegt?
Bane19
1
@GauravShankar 2 ^ 100 = 2 ^ (10 ^ 2) ist bereits größer als 10 ^ 30. Sie werden nicht sehen, wie die Berechnung abgeschlossen ist, egal auf welcher Turingmaschine Sie sie berechnen werden.
Karl Richter
31

Eigentlich habe ich Code geschrieben, der das tut, wonach Sie in O (1) fragen. Die Frage ist , was Sie vorhaben zu tun als nächstes mit dem Set. Wenn Sie es nur aufrufen size()wollen, ist das O (1), aber wenn Sie es wiederholen wollen, ist das offensichtlich O(2^n).

contains()wäre O(n)usw.

Benötigen Sie das wirklich?

BEARBEITEN:

Dieser Code ist jetzt in Guava verfügbar und wird über die Methode verfügbar gemachtSets.powerSet(set) .

Kevin Bourrillion
quelle
Ich muss über jede Teilmenge iterieren
Manuel Araoz
Aber müssen Sie jede Teilmenge speichern ?
Finnw
2
Diese Methode ist jetzt in Guave: guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/…
Kevin Bourrillion
Was ist, wenn ich nur die Powersets mit genau k Elementen haben möchte? Ist Ihr Code dafür effizient?
Eyal
Neuer Link (Guave nach Github umgezogen)
Yiwei
12

Hier ist eine Lösung, bei der ich einen Generator verwende. Der Vorteil ist, dass der gesamte Stromversorgungssatz niemals auf einmal gespeichert wird. Sie können ihn also einzeln durchlaufen, ohne dass er im Speicher gespeichert werden muss. Ich würde gerne denken, dass es eine bessere Option ist ... Beachten Sie, dass die Komplexität gleich ist, O (2 ^ n), aber der Speicherbedarf reduziert ist (vorausgesetzt, der Garbage Collector verhält sich !;))

/**
 *
 */
package org.mechaevil.util.Algorithms;

import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author st0le
 *
 */
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
    private E[] arr = null;
    private BitSet bset = null;

    @SuppressWarnings("unchecked")
    public PowerSet(Set<E> set)
    {
        arr = (E[])set.toArray();
        bset = new BitSet(arr.length + 1);
    }

    @Override
    public boolean hasNext() {
        return !bset.get(arr.length);
    }

    @Override
    public Set<E> next() {
        Set<E> returnSet = new TreeSet<E>();
        for(int i = 0; i < arr.length; i++)
        {
            if(bset.get(i))
                returnSet.add(arr[i]);
        }
        //increment bset
        for(int i = 0; i < bset.size(); i++)
        {
            if(!bset.get(i))
            {
                bset.set(i);
                break;
            }else
                bset.clear(i);
        }

        return returnSet;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not Supported!");
    }

    @Override
    public Iterator<Set<E>> iterator() {
        return this;
    }

}

Verwenden Sie dieses Muster, um es aufzurufen:

        Set<Character> set = new TreeSet<Character> ();
        for(int i = 0; i < 5; i++)
            set.add((char) (i + 'A'));

        PowerSet<Character> pset = new PowerSet<Character>(set);
        for(Set<Character> s:pset)
        {
            System.out.println(s);
        }

Es ist aus meiner Project Euler Library ... :)

st0le
quelle
Die Guave funktioniert ähnlich wie diese, ist jedoch auf 32 Elemente beschränkt. Das ist nicht unangemessen, da 2 ** 32 wahrscheinlich zu viele Iterationen sind. Es benötigt noch weniger Speicher als Ihr Speicher, da das AbstractSet nur bei Bedarf generiert wird. Versuchen Sie Ihren Code gegen die Guave, bei der Sie nur 1 von 10.000 Elementen drucken, und machen Sie ein großes Beispiel. Ich wette, dass die Guave schneller sein wird.
Eyal
@Eyal, ich bin mir sicher, ich habe nie etwas anderes behauptet. Ich habe das selbst geschrieben, es ist nicht für Produktionscode gedacht. Es war eine Übung in Algorithmen.
st0le
1
Kleinere Bemerkung: Ihr 'returnSet' ist ein TreeSet, dessen Elemente vergleichbar sein müssen. Dies ist möglicherweise nicht der Fall. Erwägen Sie, es gegen ein HashSet oder LinkedHashSet auszutauschen
Joris Kinable
10

Wenn n <63 ist, was eine vernünftige Annahme ist, da Ihnen der Speicherplatz ausgeht (es sei denn, Sie verwenden eine Iterator-Implementierung) und Sie versuchen, den Leistungssatz trotzdem zu erstellen, ist dies eine präzisere Methode. Binäre Operationen sind viel schneller als Math.pow()und Arrays für Masken, aber irgendwie haben Java-Benutzer Angst vor ihnen ...

List<T> list = new ArrayList<T>(originalSet);
int n = list.size();

Set<Set<T>> powerSet = new HashSet<Set<T>>();

for( long i = 0; i < (1 << n); i++) {
    Set<T> element = new HashSet<T>();
    for( int j = 0; j < n; j++ )
        if( (i >> j) % 2 == 1 ) element.add(list.get(j));
    powerSet.add(element); 
}

return powerSet;
Andrew Mao
quelle
Die Beendigungsbedingung in einer for-Schleife sollte i <(2 << n - 1) anstelle von i <(1 << n - 1) sein.
Bazeusz
Danke @bazeusz, ich habe es geändert, i < (1 << n)was gleichwertig ist.
Andrew Mao
9

Hier ist ein Tutorial, das genau beschreibt, was Sie wollen, einschließlich des Codes. Sie haben insofern Recht, als die Komplexität O (2 ^ n) ist.

Adamski
quelle
2
Ist das nicht Komplexität (n * 2 ^ n)? Da die Binärzeichenfolge die Länge n hat und in jeder Iteration der Hauptschleife die gesamte Binärzeichenfolge iteriert.
Maggie
1
Das Tutorial ist großartig, ABER ich habe diese Technik zur Lösung des HackerRank-Problems verwendet: Es hat nur die Hälfte der Testfälle bestanden, und die andere Hälfte ist aufgrund eines Timeouts fehlgeschlagen oder hat einen Laufzeitfehler verursacht.
Eugenie Orzini
7

Ich habe eine andere Lösung gefunden, die auf den Ideen von @Harry He basiert. Wahrscheinlich nicht das eleganteste, aber hier geht es so, wie ich es verstehe:

Nehmen wir das klassische einfache Beispiel PowerSet von SP (S) = {{1}, {2}, {3}}. Wir wissen, dass die Formel zum Erhalten der Anzahl von Teilmengen 2 ^ n (7 + leere Menge) ist. Für dieses Beispiel 2 ^ 3 = 8 Teilmengen.

Um jede Teilmenge zu finden, müssen wir 0-7 Dezimalzahlen in Binärdarstellungen konvertieren, die in der folgenden Konvertierungstabelle aufgeführt sind:

Umrechnungstabelle

Wenn wir die Tabelle zeilenweise durchlaufen, führt jede Zeile zu einer Teilmenge, und die Werte jeder Teilmenge stammen aus den aktivierten Bits.

Jede Spalte im Abschnitt Bin Value entspricht der Indexposition im ursprünglichen Eingabesatz.

Hier mein Code:

public class PowerSet {

/**
 * @param args
 */
public static void main(String[] args) {
    PowerSet ps = new PowerSet();
    Set<Integer> set = new HashSet<Integer>();
    set.add(1);
    set.add(2);
    set.add(3);
    for (Set<Integer> s : ps.powerSet(set)) {
        System.out.println(s);
    }
}

public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
    // Original set size e.g. 3
    int size = originalSet.size();
    // Number of subsets 2^n, e.g 2^3 = 8
    int numberOfSubSets = (int) Math.pow(2, size);
    Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
    ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
    for (int i = 0; i < numberOfSubSets; i++) {
        // Get binary representation of this index e.g. 010 = 2 for n = 3
        String bin = getPaddedBinString(i, size);
        //Get sub-set
        Set<Integer> set = getSet(bin, originalList));
        sets.add(set);
    }
    return sets;
}

//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
    Set<Integer> result = new HashSet<Integer>();
    for(int i = bin.length()-1; i >= 0; i--){
        //Only get sub-sets where bool flag is on
        if(bin.charAt(i) == '1'){
            int val = origValues.get(i);
            result.add(val);
        }
    }
    return result;
}

//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
    String bin = Integer.toBinaryString(i);
    bin = String.format("%0" + size + "d", Integer.parseInt(bin));
    return bin;
}

}
Adolfo Perez
quelle
5

Wenn Sie Eclipse-Sammlungen (früher GS-Sammlungen ) verwenden, können Sie die powerSet()Methode für alle SetIterables verwenden.

MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Hinweis: Ich bin ein Committer für Eclipse-Sammlungen.

Craig P. Motlin
quelle
Können Sie den Code Ihrer Lösung teilen und erklären?
Konrad Höffner
3
Sie können den Code hier
durchsehen
4

Ich suchte nach einer Lösung, die nicht so groß war wie die hier veröffentlichten. Dies zielt auf Java 7 ab, sodass für die Versionen 5 und 6 eine Handvoll Pasten erforderlich sind.

Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
    Set<Set<Object>> powerSet = new HashSet<>(),
        runSet = new HashSet<>(),
        thisSet = new HashSet<>();

    while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
        if (powerSet.isEmpty()) {
            for (Object o : orig) {
                Set<Object> s = new TreeSet<>();
                s.add(o);
                runSet.add(s);
                powerSet.add(s);
            }
            continue;
        }
        for (Object o : orig) {
            for (Set<Object> s : runSet) {
                Set<Object> s2 = new TreeSet<>();
                s2.addAll(s);
                s2.add(o);
                powerSet.add(s2);
                thisSet.add(s2);
            }
        }
        runSet.clear();
        runSet.addAll(thisSet);
        thisSet.clear();
    }
    powerSet.add(new TreeSet());
    return powerSet;

Hier ist ein Beispielcode zum Testen:

Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
    System.out.println(Arrays.toString(s.toArray()));
}
Ben
quelle
Fehlt powerSetofNodes () am Ende nicht ein "}"?
Peter Mortensen
3

Einige der oben genannten Lösungen leiden, wenn die Größe des Satzes groß ist, weil sie viel Objektmüll erzeugen, der gesammelt werden muss, und das Kopieren von Daten erfordern. Wie können wir das vermeiden? Wir können die Tatsache ausnutzen, dass wir wissen, wie groß die Größe der Ergebnismenge sein wird (2 ^ n), ein so großes Array vorab zuweisen und einfach an das Ende anhängen, ohne es zu kopieren.

Die Beschleunigung wächst schnell mit n. Ich habe es mit der obigen Lösung von João Silva verglichen. Auf meiner Maschine (alle Messungen ungefähr) ist n = 13 5x schneller, n = 14 ist 7x, n = 15 ist 12x, n = 16 ist 25x, n = 17 ist 75x, n = 18 ist 140x. Das Erstellen / Sammeln und Kopieren von Müll dominiert also bei scheinbar ähnlichen Big-O-Lösungen.

Die Vorbelegung des Arrays am Anfang scheint ein Gewinn zu sein, verglichen mit dem dynamischen Wachstum. Mit n = 18 dauert das dynamische Wachstum insgesamt etwa doppelt so lange.

public static <T> List<List<T>> powerSet(List<T> originalSet) {
    // result size will be 2^n, where n=size(originalset)
    // good to initialize the array size to avoid dynamic growing
    int resultSize = (int) Math.pow(2, originalSet.size());
    // resultPowerSet is what we will return
    List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);

    // Initialize result with the empty set, which powersets contain by definition
    resultPowerSet.add(new ArrayList<T>(0)); 

    // for every item in the original list
    for (T itemFromOriginalSet : originalSet) {

        // iterate through the existing powerset result
        // loop through subset and append to the resultPowerset as we go
        // must remember size at the beginning, before we append new elements
        int startingResultSize = resultPowerSet.size();
        for (int i=0; i<startingResultSize; i++) {
            // start with an existing element of the powerset
            List<T> oldSubset = resultPowerSet.get(i);

            // create a new element by adding a new item from the original list
            List<T> newSubset = new ArrayList<T>(oldSubset);
            newSubset.add(itemFromOriginalSet);

            // add this element to the result powerset (past startingResultSize)
            resultPowerSet.add(newSubset);
        }
    }
    return resultPowerSet;
}
George Fairbanks
quelle
3

Die folgende Lösung stammt aus meinem Buch " Coding Interviews: Questions, Analysis & Solutions ":

Es werden einige Ganzzahlen in einem Array ausgewählt, die eine Kombination bilden. Ein Satz von Bits wird verwendet, wobei jedes Bit für eine ganze Zahl im Array steht. Wenn das i-te Zeichen für eine Kombination ausgewählt ist, ist das i-te Bit 1; Andernfalls ist es 0. Beispielsweise werden drei Bits für Kombinationen des Arrays [1, 2, 3] verwendet. Wenn die ersten beiden ganzen Zahlen 1 und 2 ausgewählt werden, um eine Kombination [1, 2] zu bilden, sind die entsprechenden Bits {1, 1, 0}. In ähnlicher Weise sind Bits, die einer anderen Kombination [1, 3] entsprechen, {1, 0, 1}. Wir können alle Kombinationen eines Arrays mit der Länge n erhalten, wenn wir alle möglichen Kombinationen von n Bits erhalten können.

Eine Zahl besteht aus einer Reihe von Bits. Alle möglichen Kombinationen von n Bits entsprechen Zahlen von 1 bis 2 ^ n -1. Daher entspricht jede Zahl im Bereich zwischen 1 und 2 ^ n -1 einer Kombination eines Arrays mit der Länge n . Beispielsweise besteht die Zahl 6 aus den Bits {1, 1, 0}, sodass das erste und das zweite Zeichen im Array [1, 2, 3] ausgewählt werden, um die Kombination [1, 2] zu erzeugen. Ebenso entspricht die Zahl 5 mit den Bits {1, 0, 1} der Kombination [1, 3].

Der Java-Code zum Implementieren dieser Lösung sieht wie folgt aus:

public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) {
    ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>(); 
    BitSet bits = new BitSet(numbers.length);
    do{
        combinations.add(getCombination(numbers, bits));
    }while(increment(bits, numbers.length));

    return combinations;
}

private static boolean increment(BitSet bits, int length) {
    int index = length - 1;

    while(index >= 0 && bits.get(index)) {
        bits.clear(index);
        --index;
    }

    if(index < 0)
        return false;

    bits.set(index);
    return true;
}

private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){
    ArrayList<Integer> combination = new ArrayList<Integer>();
    for(int i = 0; i < numbers.length; ++i) {
        if(bits.get(i))
            combination.add(numbers[i]);
    }

    return combination;
}

Das Methodeninkrement erhöht eine Zahl, die in einem Satz von Bits dargestellt wird. Der Algorithmus löscht 1 Bit aus dem Bit ganz rechts, bis ein 0-Bit gefunden wird. Es setzt dann das 0-Bit ganz rechts auf 1. Um beispielsweise die Zahl 5 mit den Bits {1, 0, 1} zu erhöhen, löscht es 1 Bit von der rechten Seite und setzt das 0-Bit ganz rechts auf 1. Die Bits werden {1, 1, 0} für die Zahl 6, was das Ergebnis einer Erhöhung von 5 um 1 ist.

Harry He
quelle
Zwei Dinge, die ich geändert habe: Schleifen in getCombination anstelle von numbers.length (oder bits.size ()) kann man zu bits.length () iterieren, was die Generierung etwas beschleunigt. Schließlich habe ich die Teilmengen nach Größe sortiert, damit mein Problem dies erfordert.
BoLe
3

Hier ist eine einfache iterative O (2 ^ n) -Lösung:

public static Set<Set<Integer>> powerSet(List<Integer> intList){

    Set<Set<Integer>> result = new HashSet();
    result.add(new HashSet());

    for (Integer i : intList){

        Set<Set<Integer>> temp = new HashSet();

        for(Set<Integer> intSet : result){

            intSet = new HashSet(intSet);
            intSet.add(i);                
            temp.add(intSet);
        }
        result.addAll(temp);
    }
    return result;
}
jump3r
quelle
Diese Lösung verwendet auch O (2 ^ n) -Raum, was für große Eingabesätze zu viel wäre. Es ist besser, der rekursiven Definition zu folgen, indem Sie anstelle der Rekursion einen Stapel oder eine Warteschlange verwenden.
Rossb83
2
import java.util.Set;
import com.google.common.collect.*;

Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));
Bax
quelle
1

Wenn S eine endliche Menge mit N Elementen ist, enthält die Potenzmenge von S 2 ^ N Elemente. Die Zeit, um die Elemente des Powersets einfach aufzuzählen, beträgt 2 ^ N, also O(2^N)eine Untergrenze für die zeitliche Komplexität des (eifrigen) Aufbaus des Powersets.

Einfach ausgedrückt, jede Berechnung, bei der Powersets erstellt werden, wird nicht für große Werte von N skaliert. Kein cleverer Algorithmus hilft Ihnen ... abgesehen davon, dass Sie die Powersets nicht erstellen müssen!

Stephen C.
quelle
1

Ein Weg ohne Rekursion ist der folgende: Verwenden Sie eine Binärmaske und machen Sie alle möglichen Kombinationen.

public HashSet<HashSet> createPowerSet(Object[] array)
{
    HashSet<HashSet> powerSet=new HashSet();
    boolean[] mask= new boolean[array.length];

    for(int i=0;i<Math.pow(2, array.length);i++)
    {
        HashSet set=new HashSet();
        for(int j=0;j<mask.length;j++)
        {
            if(mask[i])
                set.add(array[j]);
        }
        powerSet.add(set);      

        increaseMask(mask);
    }

    return powerSet;
}

public void increaseMask(boolean[] mask)
{
    boolean carry=false;

    if(mask[0])
        {
            mask[0]=false;
            carry=true;
        }
    else
        mask[0]=true;

    for(int i=1;i<mask.length;i++)
    {
        if(mask[i]==true && carry==true)
        mask[i]=false;
        else if (mask[i]==false && carry==true)
        {
            mask[i]=true;
            carry=false;
        }
        else 
            break;

    }

}
Orestis
quelle
1

Algorithmus:

Eingabe: Set [], set_size 1. Ermitteln Sie die Größe der Potenzmenge powet_set_size = pow (2, set_size) 2 Schleife für Zähler von 0 bis pow_set_size (a) Schleife für i = 0 bis set_size (i) Wenn das i-te Bit im Zähler ist set Drucken Sie das i-te Element aus der Menge für diese Teilmenge. (b) Drucken Sie den Trennzeichen für Teilmengen, dh Zeilenumbruch

#include <stdio.h>
#include <math.h>
 
void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
 
    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}
 
/*Driver program to test printPowerSet*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);
 
    getchar();
    return 0;
}

gaurav
quelle
1

Dies ist meine rekursive Lösung, mit der Sie mithilfe von Java Generics die Leistung jedes Satzes abrufen können. Die Hauptidee besteht darin, den Kopf des Eingabearrays wie folgt mit allen möglichen Lösungen des restlichen Arrays zu kombinieren.

import java.util.LinkedHashSet;
import java.util.Set;

public class SetUtil {
    private static<T>  Set<Set<T>> combine(T head, Set<Set<T>> set) {
        Set<Set<T>> all = new LinkedHashSet<>();

        for (Set<T> currentSet : set) {
            Set<T> outputSet = new LinkedHashSet<>();

            outputSet.add(head);
            outputSet.addAll(currentSet);

            all.add(outputSet);
        }

        all.addAll(set);        

        return all;
    }

    //Assuming that T[] is an array with no repeated elements ...
    public static<T> Set<Set<T>> powerSet(T[] input) {
        if (input.length == 0) {
            Set <Set<T>>emptySet = new LinkedHashSet<>();

            emptySet.add(new LinkedHashSet<T>());

            return emptySet;
        }

        T head = input[0];
        T[] newInputSet = (T[]) new Object[input.length - 1];

        for (int i = 1; i < input.length; ++i) {
            newInputSet[i - 1] = input[i];
        }

        Set<Set<T>> all = combine(head, powerSet(newInputSet));

        return all;
    }

    public static void main(String[] args) {            
        Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6});

        System.out.println(set);
    }
}

Dies wird Folgendes ausgeben:

[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []]
Hazem Saleh
quelle
1

Eine weitere Beispielimplementierung:

 public static void main(String args[])
    {
        int[] arr = new int[]{1,2,3,4};
        // Assuming that number of sets are in integer range
        int totalSets = (int)Math.pow(2,arr.length);
        for(int i=0;i<totalSets;i++)
        {
            String binaryRep = Integer.toBinaryString(i);      
            for(int j=0;j<binaryRep.length();j++)
            {
                int index=binaryRep.length()-1-j;
                if(binaryRep.charAt(index)=='1')
                System.out.print(arr[j] +" ");       
            }
            System.out.println();
        }
    }
Sandeep
quelle
1

Dies ist mein Ansatz mit Lambdas.

public static <T> Set<Set<T>> powerSet(T[] set) {
      return IntStream
            .range(0, (int) Math.pow(2, set.length))
            .parallel() //performance improvement
            .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet()))
            .map(Function.identity())
            .collect(Collectors.toSet());
        }

Oder parallel (siehe Kommentar parallel ()):

Größe des Eingabesatzes: 18

Logische Prozessoren: 8 bis 3,4 GHz

Leistungsverbesserung: 30%

Werner
quelle
1

Eine Teilmenge von t ist eine beliebige Menge, die durch Entfernen von null oder mehr Elementen von t erstellt werden kann. Die Teilmenge withoutFirst fügt die Teilmengen von t hinzu, denen das erste Element fehlt, und die for-Schleife behandelt das Hinzufügen von Teilmengen mit dem ersten Element. Wenn t beispielsweise die Elemente ["1", "2", "3"] enthält, fügt "MissingFirst" [[""], ["2"], ["3"], ["2", "3" hinzu "]] und die for-Schleife kleben die" 1 "vor dieses Element und fügen sie dem newSet hinzu. Also werden wir am Ende [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"] haben. , ["2", "3"], ["1", "2", "3"]].

public static Set<Set<String>> allSubsets(Set<String> t) {
        Set<Set<String>> powerSet = new TreeSet<>();
        if(t.isEmpty()) {
            powerSet.add(new TreeSet<>());
            return powerSet;
        }
        String first = t.get(0);
        Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size()));
        for (List<String> 1st : withoutFirst) {
            Set<String> newSet = new TreeSet<>();
            newSet.add(first);
            newSet.addAll(lst);
            powerSet.add(newSet);
        }
        powerSet.addAll(withoutFirst);
        return powerSet;
    }
Hassan Alhujhoj
quelle
Bitte fügen Sie dem von Ihnen angegebenen Code eine kurze Erklärung hinzu.
Mirza Sisic
Dies wird nicht einmal kompiliert, scheint in einer Fantasy-Java-Version geschrieben zu sein. Sethat weder eine getMethode mit einem Index noch eine subSetMethode; 1stist keine gültige Kennung (ich nehme an, lstwar gemeint). Ändern Sie alle Sätze in Listen und es wird fast kompiliert ...
John16384
0
// input: S
// output: P
// S = [1,2]
// P = [], [1], [2], [1,2]

public static void main(String[] args) {
    String input = args[0];
    String[] S = input.split(",");
    String[] P = getPowerSet(S);
    if (P.length == Math.pow(2, S.length)) {
        for (String s : P) {
            System.out.print("[" + s + "],");
        }
    } else {
        System.out.println("Results are incorrect");
    }
}

private static String[] getPowerSet(String[] s) {
    if (s.length == 1) {
        return new String[] { "", s[0] };
    } else {
        String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length));
        String[] subP2 = new String[subP1.length];
        for (int i = 0; i < subP1.length; i++) {
            subP2[i] = s[0] + subP1[i];
        }
        String[] P = new String[subP1.length + subP2.length];
        System.arraycopy(subP1, 0, P, 0, subP1.length);
        System.arraycopy(subP2, 0, P, subP1.length, subP2.length);
        return P;
    }

}
Neyyadupakkam Sundarasekaran
quelle
Willkommen bei Stack Overflow. Vielleicht möchten Sie diese Antwort ein wenig mit einem Text ausarbeiten, der beschreibt, was sie tut und wie sie das Problem des Fragestellers löst.
Lachlan Goodhew-Cook
0

Ich musste kürzlich so etwas verwenden, brauchte aber zuerst die kleinsten Unterlisten (mit 1 Element, dann 2 Elementen, ...). Ich wollte weder die leere noch die ganze Liste aufnehmen. Außerdem brauchte ich keine Liste aller zurückgegebenen Unterlisten, ich musste nur ein paar Sachen mit jeder machen.

Wollte dies ohne Rekursion tun und fand Folgendes (wobei das "Doing Stuff" in eine funktionale Schnittstelle abstrahiert wurde):

@FunctionalInterface interface ListHandler<T> {
    void handle(List<T> list);
}


public static <T> void forAllSubLists(final List<T> list, ListHandler handler) {
    int     ll = list.size();   // Length of original list
    int     ci[] = new int[ll]; // Array for list indices
    List<T> sub = new ArrayList<>(ll);  // The sublist
    List<T> uml = Collections.unmodifiableList(sub);    // For passing to handler

    for (int gl = 1, gm; gl <= ll; gl++) {  // Subgroup length 1 .. n-1
        gm = 0; ci[0] = -1; sub.add(null);  // Some inits, and ensure sublist is at least gl items long

        do {
                ci[gm]++;                       // Get the next item for this member

                if (ci[gm] > ll - gl + gm) {    // Exhausted all possibilities for this position
                        gm--; continue;         // Continue with the next value for the previous member
                }

                sub.set(gm, list.get(ci[gm]));  // Set the corresponding member in the sublist

                if (gm == gl - 1) {             // Ok, a sublist with length gl
                        handler.handle(uml);    // Handle it
                } else {
                        ci[gm + 1] = ci[gm];    // Starting value for next member is this 
                        gm++;                   // Continue with the next member
                }
        } while (gm >= 0);  // Finished cycling through all possibilities
    }   // Next subgroup length
}

Auf diese Weise ist es auch einfach, es auf Unterlisten bestimmter Längen zu beschränken.

tijmen
quelle
0
public class PowerSet {
    public static List<HashSet<Integer>> powerset(int[] a) {
        LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>();
        int n = a.length;
        for (int i = 0; i < 1 << n; i++) {
            HashSet<Integer> set = new HashSet<Integer>();
            for (int j = 0; j < n; j++) {
                if ((1 << j & i) > 0)
                    set.add(a[j]);
            }
            sets.add(set);
        }
        return sets;
    }

    public static void main(String[] args) {
        List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 });
        for (HashSet<Integer> set : sets) {
            for (int i : set)
                System.out.print(i);
            System.out.println();
        } 
    }
}
Selim Ekizoglu
quelle
0

Noch eine andere Lösung - mit Java8 + Streaming-API Es ist faul und geordnet, so dass es korrekte Teilmengen zurückgibt, wenn es mit "limit ()" verwendet wird.

 public long bitRangeMin(int size, int bitCount){
    BitSet bs = new BitSet(size);
    bs.set(0, bitCount);
    return bs.toLongArray()[0];
}

public long bitRangeMax(int size, int bitCount){
    BitSet bs = BitSet.valueOf(new long[]{0});
    bs.set(size - bitCount, size);
    return bs.toLongArray()[0];
}

public <T> Stream<List<T>> powerSet(Collection<T> data)
{
    List<T> list = new LinkedHashSet<>(data).stream().collect(Collectors.toList());
    Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i}));
    Stream<BitSet> tail = IntStream.rangeClosed(1, list.size())
            .boxed()
            .flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1))
                    .mapToObj(v2 -> BitSet.valueOf(new long[]{v2}))
                    .filter( bs -> bs.cardinality() == v1));

    return Stream.concat(head, tail)
            .map( bs -> bs
                    .stream()
                    .mapToObj(list::get)
                    .collect(Collectors.toList()));
}

Und der Client-Code ist

@Test
public void testPowerSetOfGivenCollection(){
    List<Character> data = new LinkedList<>();
    for(char i = 'a'; i < 'a'+5; i++ ){
        data.add(i);
    }
    powerSet(data)
            .limit(9)
            .forEach(System.out::print);

}

/ * Drucke: [] [a] [b] [c] [d] [e] [a, b] [a, c] [b, c] * /

Ekobir
quelle
0

Wir könnten den Potenzsatz mit oder ohne Rekursion schreiben. Hier ist ein Versuch ohne Rekursion:

public List<List<Integer>> getPowerSet(List<Integer> set) {
    List<List<Integer>> powerSet = new ArrayList<List<Integer>>();
    int max = 1 << set.size();
    for(int i=0; i < max; i++) {
        List<Integer> subSet = getSubSet(i, set);
        powerSet.add(subSet);
    }
    return powerSet;
}

private List<Integer> getSubSet(int p, List<Integer> set) {
    List<Integer> subSet = new ArrayList<Integer>();
    int position = 0;
    for(int i=p; i > 0; i >>= 1) {
        if((i & 1) == 1) {
            subSet.add(set.get(position));
        }
        position++;
    }
    return subSet;
}
YuVi
quelle
0

Hier soll ein Stromsatz erzeugt werden. Die Idee ist zuerst = S[0]und kleinere Mengen werden S[1,...n].

Berechnen Sie alle Teilmengen von kleinerem Satz und fügen Sie sie in alle Teilmengen ein.

Klonen Sie jede Teilmenge in allen Teilmengen und fügen Sie sie zuerst zur Teilmenge hinzu.

ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, int index){
    ArrayList<ArrayList<Integer>> allsubsets;
    if(set.size() == index){
        allsubsets = new ArrayList<ArrayList<Integer>>();
        allsubsets.add(new ArrayList<Integer>()); // the empty set 
    }else{
        allsubsets = getSubsets(set, index+1);
        int item = set.get(index);

        ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();

        for(ArrayList<Integer> subset: allsubsets){
            ArrayList<Integer> newsubset = new ArrayList<Integer>();

            newsubset.addAll(subset);
            newsubset.add(item);
            moresubsets.add(newsubset);

        }

        moresubsets.addAll(moresubsets);

    }

    return allsubsets;
}
Keiner
quelle
0
package problems;

import java.util.ArrayList;
import java.util.List;

public class SubsetFinderRecursive {
    public static void main(String[] args) {
        //input
        int[] input = new int[3];
        for(int i=0; i<input.length; i++) {
            input[i] = i+1;
        }
        // root node of the tree
        Node root = new Node();

        // insert values into tree
        for(int i=0; i<input.length; i++) {
            insertIntoTree(root, input[i]);
        }

        // print leaf nodes for subsets
        printLeafNodes(root);
    }

    static void printLeafNodes(Node root) {

        if(root == null) {
            return;
        }

        // Its a leaf node
        if(root.left == null && root.right == null) {
            System.out.println(root.values);
            return;
        }

        // if we are not at a leaf node, then explore left and right

        if(root.left !=null) {
            printLeafNodes(root.left);
        }

        if(root.right != null) {
            printLeafNodes(root.right);
        }
    }

    static void insertIntoTree(Node root, int value) {

        // Error handling
        if(root == null) {
            return;
        }

        // if there is a sub tree then go down
        if(root.left !=null && root.right != null) {
            insertIntoTree(root.left, value);
            insertIntoTree(root.right, value);
        }

        // if we are at the leaf node, then we have 2 choices
        // Either exclude or include
        if(root.left == null && root.right == null) {
            // exclude
            root.left = new Node();
            root.left.values.addAll(root.values);
            // include
            root.right = new Node();
            root.right.values.addAll(root.values);
            root.right.values.add(value);
            return;
        }
    }

}

class Node {
    Node left;
    Node right;
    List<Integer> values = new ArrayList<Integer>();
}
Prakash Devta
quelle