Получение степенного множества набора в Java
Для определения обычного друга функции в шаблонах классов нужно особое внимание:
template
class Creator {
friend void appear() { // a new function ::appear(), but it doesn't
… // exist until Creator is instantiated
}
};
Creator miracle; // ::appear() is created at this point
Creator oops; // ERROR: ::appear() is created a second time!
В этом примере, два различных инстанцирования создают два идентичных definitions— прямое нарушение ODR
, Мы должны поэтому удостовериться, что шаблонные параметры шаблона класса появляются в типе любого друга функция, определяемая в том шаблоне (если мы не хотим предотвратить больше чем одно инстанцирование шаблона класса в конкретном файле, но это довольно маловероятно). Давайте применим это к изменению нашего предыдущего примера:
template
class Creator {
friend void feed(Creator*){ // every T generates a different
… // function ::feed()
}
};
Creator one; // generates ::feed(Creator*)
Creator two; // generates ::feed(Creator*)
Правовая оговорка: Я вставил этот раздел от Шаблоны C++: полное руководство / Раздел 8.4
5 ответов
Да, это действительно 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);
}
Здесь - это руководство, в котором точно описано, что вы хотите, включая код. Вы правы в том, что сложность O (2 ^ n).
Actually, I've written code that does what you're asking for in O(1). The question is what you plan to do with the Set next. If you're just going to call size() on it, that's O(1), but if you're going to iterate it that's obviously O(2^n).
contains() would be O(n), etc.
Do you really need this?
EDIT:
This code is now available in Guava, exposed through the method Sets.powerSet(set).
If S is a finite set with N elements, then the power set of S contains 2^N elements. The time to simply enumerate the elements of the powerset is 2^N, so O(2^N) is a lower bound on the time complexity of (eagerly) constructing the powerset.
Put simply, any computation that involves creating powersets is not going to scale for large values of N. No clever algorithm will help you ... apart from avoiding the need to create the powersets!
Вот решение, в котором я использую генератор, преимущество в том, что весь набор мощности никогда не сохраняется сразу ... Таким образом, вы можете перебирать его один за другим, не сохраняя его в памяти. Я бы хотел подумать, что это лучший вариант ... Обратите внимание, что сложность такая же, 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);
}
Это из моей библиотеки Project Euler ... :)