在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函數？(我認為可能是O(2^n)。)
3 回答
慕俠2389804
TA貢獻1719條經驗 獲得超6個贊
O(2^n)2^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);
}
心有法竹
TA貢獻1866條經驗 獲得超5個贊
/**
*
*/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);
}添加回答
舉報
0/150
提交
取消