首頁(yè) 猿問(wèn) 在Java中獲取一個(gè)集的Powerset

在Java中獲取一個(gè)集的Powerset

Sass/Less Java

30秒到達(dá)戰(zhàn)場(chǎng) 2019-08-03 03:03:47

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

查看完整描述

3 回答

慕俠2389804

TA貢獻(xiàn)1719條經(jīng)驗(yàn) 獲得超6個(gè)贊

是的，是的O(2^n)實(shí)際上，既然你需要生成，2^n可能的組合。下面是一個(gè)工作實(shí)現(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;}

以及一個(gè)測(cè)試，給出您的示例輸入：

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

反對(duì) 回復(fù) 2019-08-04

心有法竹

TA貢獻(xiàn)1866條經(jīng)驗(yàn) 獲得超5個(gè)贊

這里有一個(gè)解決方案，我使用發(fā)電機(jī)，優(yōu)點(diǎn)是，整個(gè)功率集從來(lái)沒(méi)有存儲(chǔ)在一次.。因此，您可以一個(gè)地迭代它，而不需要將它存儲(chǔ)在內(nèi)存中。我想這是個(gè)更好的選擇.。注意復(fù)雜性是相同的，O(2^n)，但是內(nèi)存需求減少了(假設(shè)垃圾收集器運(yù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;
    }}

要調(diào)用它，請(qǐng)使用以下模式：

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

這是我的歐拉項(xiàng)目圖書(shū)館.。*)

反對(duì) 回復(fù) 2019-08-04