Вопрос-ответ

Obtaining a powerset of a set in Java

Получение набора полномочий для набора в Java

Набор полномочий для {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).)

Переведено автоматически
Ответ 1

Да, это 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);
}
Ответ 2

На самом деле, я написал код, который выполняет то, что вы просите в O (1). Вопрос в том, что вы планируете делать с набором дальше. Если вы просто собираетесь вызвать size() для этого, это O (1), но если вы собираетесь повторить это, это очевидно O(2^n).

contains() было бы O(n) и т.д.

Вам действительно это нужно?

Редактировать:

Этот код теперь доступен в Guava, доступен с помощью метода Sets.powerSet(set).

Ответ 3

Вот решение, в котором я использую генератор, преимущество которого в том, что весь набор полномочий никогда не сохраняется сразу... Таким образом, вы можете перебирать его один за другим, не требуя его сохранения в памяти. Я хотел бы думать, что это лучший вариант... Обратите внимание, что сложность та же, 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);
}

Это из библиотеки моего проекта Euler ... :)

Ответ 4

Если n < 63, что является разумным предположением, поскольку у вас все равно закончилась бы память (если только вы не используете реализацию итератора) при попытке создать набор полномочий, это более краткий способ сделать это. Двоичные операции намного быстрее, чем Math.pow() и массивы для масок, но почему-то пользователи Java их боятся...

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;
java algorithm