L'obtention d'un ensemble des parties d'un ensemble en Java

Question

L'ensemble des parties de l' {1, 2, 3} est:

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

Disons que j'ai un Set en Java:

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

Comment puis-je écrire la fonction getPowerset, avec le meilleur ordre possible de la complexité? (Je pense qu'il pourrait être O(2^n).)

Answer 1

Oui, c'est - O(2^n) en effet, depuis que vous avez besoin pour générer, bien, 2^n combinaisons possibles. Voici un travail de mise en œuvre, l'utilisation de génériques et de jeux:

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

Et un test, étant donné que votre exemple d'entrée:

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

Answer 2

Manuel,

En fait, j'ai écrit un code qui fait ce que vous demandez en O(1). La question est de savoir ce que vous comptez faire avec le Jeu suivant. Si vous êtes juste de l'appeler size (), c'est O(1), mais si vous allez à la parcourir, c'est évidemment O(2^n).

contient du (de la) serait en O(n), etc.

Avez-vous vraiment besoin de cela?

EDIT: Ce code est maintenant disponible dans la Goyave.

Answer 3

Voici une solution où j'utilise un générateur, l'avantage étant, la totalité de la puissance n'est jamais stocké à la fois... de Sorte que vous pouvez parcourir un par un, sans avoir besoin d'être stockées dans la mémoire. J'aime à penser que c'est une meilleure option... à Noter la complexité est la même, O(2^n), mais les besoins en mémoire sont réduits (en supposant que le garbage collector se comporte! ;) )

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

}

Pour l'appeler, de l'utilisation de ce modèle:

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

C'est à partir de mon Projet Euler Bibliothèque... :)

Answer 4

Si n < 63, qui est une hypothèse raisonnable depuis que vous aviez exécuter de mémoire (à moins d'utiliser un itérateur de mise en œuvre) en essayant de construire la puissance de toute façon, c'est une manière plus concise de le faire. Les opérations binaires sont plus rapides que d' Math.pow() et les tableaux pour les masques, mais de toute façon utilisateurs Java ont peur d'eux...

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;

Answer 5

Ici est un tutoriel décrivant exactement ce que vous voulez, y compris le code. Vous avez raison en est que la complexité est O(2^n).