Нахождение определенного набора подсетей PowerSet эффективным способом - PullRequest
Новая
       5

Нахождение определенного набора подсетей PowerSet эффективным способом

2 голосов
/ 23 сентября 2011

Я пытаюсь найти эффективный способ получить набор подмножеств PowerSet.

Например, это работает, когда размеры набора невелики: 

Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);

Set<Integer> set2 = new HashSet<Integer>();
set2.add(3);


Set<Set<Integer>> sets = MyUtils.powerSet(set); //size - 8 SubSets
Set<Set<Integer>> badSets = MyUtils.powerSet(set2); //size - 2 SubSets

//my set of subsets of the powerset
sets.removeAll(badSets) //size - 6 SubSets

Однако, когда в эти наборы добавляется больше элементов, это не становится практичным.Есть ли другой способ сделать это?

Просто дружеское напоминание о том, что такое PowerSet:

PowerSet of {a, b, c}:

P (S) ={{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

Ответы [ 4 ]

3 голосов
/ 24 сентября 2011

Если один набор является подмножеством другого (размеры A, B, m, n) после удаления P (B) из P (A), у вас есть 2 n - 2 m элемент, также, если B не является подмножеством A, снова вы можете принять B'=A intersection with B, и снова мы имеем аналогичное отношение, так что числа большие во всем.

например, предположим, что A-B имеет один элемент, | P (A) -P (B) | = 2 n - 2 (n-1) = 2 (n-1) , например, для n = 40 вы не можете перебирать все элементы .

в любом случае, один из способов, как показано ниже:

У

есть счетчик размера n в базе 2, сначала установите m + 1 бит как 1, а все остальные как 0, затем напечатайте результат, и каждый раз увеличивайте счетчик (на единицу) и печатайте результат до богатого до 2 n - 1 . который является O (2 n - 2 m ).

1 голос
/ 23 сентября 2011

Попробуйте другой способ:

позвольте вызову set3 = set - set2;

Затем Powerset (set) - Poserset (set2) = Powerset (set3) x (Powerset (set) - {});

где x здесь - это Декарт, кратный 2 множеству.

если в set3 есть элемент x, в set2 есть элемент y, то при таком подходе сложность составляет около 2 ^ (x + y), а если попытаться удалить его напрямую, сложность составляет около 2 ^ (x + 2Y).

Hth.

1 голос
/ 23 сентября 2011

Походит на работу для диаграмм с подавленным нулем решения.Они поддерживают вычитание наборов, и создание набора мощности из ряда чисел тривиально в ZDD (и фактически в результате ZDD имеет очень мало узлов).Это означает, что асимметричное различие также будет работать быстро, потому что оно работает на двух маленьких ZDD и зависит только от размера ZDD в узлах, а не от количества наборов, которые они содержат.Я не знаю, что вы собираетесь делать с этим дальше, но что бы это ни было, вы всегда можете перечислить все наборы в ZDD и поместить их в другую структуру данных.

0 голосов
/ 23 сентября 2011

Для вычитания одного набора мощности из другого, вычисление вычтенного набора мощности является избыточным. Вот путь: 

public static <T>void removePowerSet(
        Collection <? extends Collection <T>> powerSet,
        Collection <T> removedComponents){
    Iterator <? extends Collection <T>> powerSetIter = powerSet.iterator();
    while (powerSetIter.hasNext()) {
        Collection <T> powerSetSubset = powerSetIter.next();
        if (removedComponents.containsAll(powerSetSubset)) {
            powerSetIter.remove();
        }
    }
}

Этот алгоритм выполняет за полиномиальное время - O (n 2 ) для HashSet

Теперь вы можете позвонить removePowerSet(sets, set2) или removePowerSet(sets, Arrays.asList(3)), чтобы получить результат в вашем примере.

...