首頁猿問在Java中獲取一個集的Powerset

在Java中獲取一個集的Powerset

Java 算法

海綿寶寶撒 2019-07-11 16:48:53

在Java中獲取一個集的Powerset.的權力集{1, 2, 3}是：{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}假設我有一個Set在Java中：Set<Integer> mySet = new HashSet<Integer>();mySet.add(1);mySet.add(2);mySet.add(3);Set<Set<Integer>> powerSet = getPowerset(mySet);如何用盡可能好的復雜性順序編寫getPowerset函數(shù)？(我認為可能是O(2^n)。)

查看完整描述

3 回答

斯蒂芬大帝

TA貢獻1827條經(jīng)驗獲得超8個贊

是的，是的O(2^n)實際上，既然你需要生成，2^n可能的組合。下面是一個工作實現(xiàn)，使用泛型和集合：

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

以及一個測試，給出您的示例輸入：

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

反對回復 2019-07-11

慕仙森

TA貢獻1827條經(jīng)驗獲得超8個贊

這里有一個解決方案，我使用發(fā)電機，優(yōu)點是，整個功率集從來沒有存儲在一次.。因此，您可以一個地迭代它，而不需要將它存儲在內存中。我想這是個更好的選擇.。注意復雜性是相同的，O(2^n)，但是內存需求減少了(假設垃圾收集器運行！；)

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

要調用它，請使用以下模式：

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

這是我的歐拉項目圖書館.。*)

反對回復 2019-07-11