Erhalt einer powerset von einem Satz in Java

Ja, es ist O(2^n) ja, da müssen Sie zu generieren, sowie, 2^n möglichen Kombinationen. Hier ist eine funktionierende Implementierung, die Verwendung von Generika und sets:

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, da dein Beispiel Eingabe:

 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);
 }

InformationsquelleAutor der Antwort João Silva

Hier ist eine Lösung, wo ich einen generator, der Vorteil, die gesamte Potenzmenge gespeichert nie auf einmal... So dass Sie können Durchlaufen Sie one-by-one, ohne dass es im Fehlerspeicher abgelegt werden. Möchte ich glaube, es ist eine bessere option... Hinweis: die Komplexität ist die gleiche, O(2^n), aber die Anforderungen an den Arbeitsspeicher reduziert werden (vorausgesetzt, dass der garbage collector verhält! 😉 )

/**
 *
 */
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;
    }

}

Ihn nennen, verwenden Sie dieses Muster:

        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 Projekt-Euler-Bibliothek... 🙂

InformationsquelleAutor der Antwort st0le

Hier ist ein tutorial beschreibt genau, was Sie wollen, einschließlich der code. Sie sind richtig, dass die Komplexität ist O(2^n).

InformationsquelleAutor der Antwort Adamski

Wenn Sie Eclipse-Sammlungen (ehemals GS Collections), können Sie die powerSet() Methode auf alle SetIterables.

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 committer für Eclipse Sammlungen.

InformationsquelleAutor der Antwort Craig P. Motlin

Folgende Lösung ist entlehnt aus meinem Buch "Coding Interviews: Questions, Analysis & Lösungen":

Einige ganze zahlen in einem array ausgewählt werden, aus denen eine Kombination. Eine Reihe von bits verwendet wird, wobei jedes bit steht für eine ganze Zahl im array. Wenn die i-TEN Zeichen ausgewählt, die für eine Kombination, die i-TEN bit 1 ist, andernfalls ist es 0. Zum Beispiel drei bits werden verwendet für Kombinationen von array [1, 2, 3]. Wenn die ersten zwei Ganzzahlen 1 und 2 ausgewählt sind, zu verfassen eine Kombination [1, 2], die entsprechenden bits sind {1, 1, 0}. Ebenso bits entspricht einer anderen Kombination [1, 3] {1, 0, 1}. Wir sind in der Lage, alle Kombinationen eines Arrays mit Länge n wenn wir alle möglichen Kombinationen von n bits.

Einer Zahl aus einem Satz von bits. Alle möglichen Kombinationen von n bits entsprechen zahlen
von 1 zu 2^n-1. Daher, jede Zahl im Bereich zwischen 1 und 2^n-1 entspricht einer Kombination aus einem array mit Länge n. Zum Beispiel die Zahl 6 besteht aus bits {1, 1, 0}, so dass die ersten und zweiten Zeichen ausgewählt, die in das array [1, 2, 3] zu generieren, die Kombination [1, 2]. Ebenso die Zahl 5 mit bits {1, 0, 1} entspricht der Kombination [1, 3].

Den Java-code zur Implementierung 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;
}

Die Methode increment-erhöht eine Zahl repräsentiert, die in einem Satz von bits. Der Algorithmus löscht 1-bits
aus dem niedrigstwertigen bit, bis ein 0-bit gefunden wird. Es setzt dann die am weitesten rechts liegenden bit 0 auf 1. Zum Beispiel, um zu erhöhen die Zahl 5 mit bits {1, 0, 1}, löscht es 1-bits von der rechten Seite und legt den niedrigstwertigen bit 0 auf 1. Die bits zu {1, 1, 0} für die Zahl 6, das ist das Resultat, dass 5 von 1.

InformationsquelleAutor der Antwort Harry He

Hier ist ein einfacher iterativer 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;
}

InformationsquelleAutor der Antwort jump3r

Wenn S eine endliche Menge mit N Elementen, dann ist die Potenzmenge von S enthält 2^N Elemente. Die Zeit, einfach aufzählen der Elemente der powerset ist 2^N, also O(2^N) ist eine untere Schranke für die Zeitkomplexität von (eifrig) Bau der powerset.

Einfach ausgedrückt, alle Berechnungen, die umfasst das erstellen powersets ist nicht Maßstab für große Werte von N. Kein ausgeklügelter Algorithmus wird Ihnen helfen, ... mal abgesehen davon dass die Notwendigkeit zu erstellen, die powersets!

InformationsquelleAutor der Antwort Stephen C

Dies ist meine rekursive Lösung, kann man die Potenzmenge jeder Satz mit Java-Generics. Seine Grundidee besteht in der Kombination der Kopf des Eingabe-array mit allen möglichen Lösungen, der rest der array wie folgt.

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);
    }
}

Dieser Ausgabe:

[[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], []]

InformationsquelleAutor der Antwort Hazem Saleh

Einem sub-Satz von t ist jeder Satz, die gemacht werden können durch das entfernen von null oder mehr Elementen von t ist. Die withoutFirst Teilmenge fügt hinzu, die Teilmengen von t sind, fehlt das erste element und die for-Schleife wird sich mit der Zugabe von Teilmengen mit dem ersten element. Zum Beispiel, wenn t enthaltenen Elemente ["1", "2", "3"], missingFirst wird, fügen Sie [[""],
["2"], ["3"], ["2","3"]] und die for-Schleife stick wird die "1" vor diesen-element und fügen Sie es in die newSet. So werden wir am Ende mit [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"], ["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;
    }

InformationsquelleAutor der Antwort Hassan Alhujhoj

Vor kurzem hatte ich Sie etwas wie dies, allerdings benötigt die kleinste Teillisten (mit 1 element, 2 Elemente, ...). Ich wollte nicht gehören das leere, noch die ganze Liste.
Auch habe ich nicht benötigen eine Liste aller Teillisten zurück, ich brauchte nur etwas mit jedem.

Wollte, dies zu tun, ohne Rekursion, und kam mit der folgenden (mit dem "Zeug" abstrahiert, in eine funktionale Schnittstelle):

@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
}

In dieser Weise, ist es auch leicht zu einer Beschränkung auf die Teillisten der Längen.

InformationsquelleAutor der Antwort tijmen

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();
        } 
    }
}

InformationsquelleAutor der Antwort Selim Ekizoglu

Könnten wir schreiben, die Kraft einstellen, mit oder ohne Verwendung von Rekursion. 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;
}

InformationsquelleAutor der Antwort YuVi