«Получение мощного набора набора в Java»

«1. Введение

В этом уроке мы изучим процесс создания набора мощности заданного набора в Java.

Напомню, что для каждого набора размера n существует набор мощностей размера 2n. Мы узнаем, как получить его, используя различные методы.

2. Определение набора мощности

Набор мощности данного набора S — это набор всех подмножеств S, включая само S и пустое множество.

Например, для данного набора:

{"APPLE", "ORANGE", "MANGO"}

набор мощности:

{
    {},
    {"APPLE"},
    {"ORANGE"},
    {"APPLE", "ORANGE"},
    {"MANGO"},
    {"APPLE", "MANGO"},
    {"ORANGE", "MANGO"},
    {"APPLE", "ORANGE", "MANGO"}
}

Поскольку это также набор подмножеств, порядок его внутренних подмножеств не важен, и они могут появиться в любом порядке:

{
    {},
    {"MANGO"},
    {"ORANGE"},
    {"ORANGE", "MANGO"},
    {"APPLE"},
    {"APPLE", "MANGO"},
    {"APPLE", "ORANGE"},
    {"APPLE", "ORANGE", "MANGO"}
}

3. Библиотека Guava

В библиотеке Google Guava есть несколько полезных утилит Set, например power set. Таким образом, мы можем легко использовать его также для получения набора мощности данного набора:

@Test
public void givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets() {
    ImmutableSet<String> set = ImmutableSet.of("APPLE", "ORANGE", "MANGO");
    Set<Set<String>> powerSet = Sets.powerSet(set);
    Assertions.assertEquals((1 << set.size()), powerSet.size());
    MatcherAssert.assertThat(powerSet, Matchers.containsInAnyOrder(
      ImmutableSet.of(),
      ImmutableSet.of("APPLE"),
      ImmutableSet.of("ORANGE"),
      ImmutableSet.of("APPLE", "ORANGE"),
      ImmutableSet.of("MANGO"),
      ImmutableSet.of("APPLE", "MANGO"),
      ImmutableSet.of("ORANGE", "MANGO"),
      ImmutableSet.of("APPLE", "ORANGE", "MANGO")
   ));
}

Guava powerSet внутренне работает через интерфейс Iterator таким образом, что когда запрашивается следующее подмножество, подмножество вычисляется и возвращается. Таким образом, сложность пространства снижается до O(n) вместо O(2n).

Но как Гуава достигает этого?

4. Подход к генерации набора мощности

4.1. Алгоритм

Давайте теперь обсудим возможные шаги для создания алгоритма для этой операции.

Степенной набор пустого набора равен {{}}, в котором он содержит только один пустой набор, так что это наш простейший случай.

Для каждого набора S, отличного от пустого, мы сначала извлекаем один элемент и называем его – элемент. Затем для остальных элементов набора subsetWithoutElement мы рекурсивно вычисляем их набор мощности — и называем его как-то вроде powerSetSubsetWithoutElement. Затем, добавляя извлеченный элемент ко всем множествам в powerSetSubsetWithoutElement, мы получаем powerSetSubsetWithElement.

Теперь набор мощностей S является объединением powerSetSubsetWithoutElement и powerSetSubsetWithElement:

Давайте посмотрим на пример рекурсивного стека набора мощностей для заданного набора {\»APPLE\», \»ORANGE\», \»МАНГО\» }.

Для улучшения читаемости изображения мы используем краткие формы имен: P означает функцию набора мощности, а «A», «O», «M» — краткие формы «APPLE», «ORANGE». и «МАНГО» соответственно:

4.2. Реализация

Итак, во-первых, давайте напишем код Java для извлечения одного элемента и получения оставшихся подмножеств:

Затем нам нужно получить набор функций subsetWithoutElement:

T element = set.iterator().next();
Set<T> subsetWithoutElement = new HashSet<>();
for (T s : set) {
    if (!s.equals(element)) {
        subsetWithoutElement.add(s);
    }
}

Затем мы необходимо добавить этот набор мощности обратно в исходный:

Set<Set<T>> powersetSubSetWithoutElement = recursivePowerSet(subsetWithoutElement);

Наконец, объединение powerSetSubSetWithoutElement и powerSetSubSetWithElement является набором мощности данного входного набора:

Set<Set<T>> powersetSubSetWithElement = new HashSet<>();
for (Set<T> subsetWithoutElement : powerSetSubSetWithoutElement) {
    Set<T> subsetWithElement = new HashSet<>(subsetWithoutElement);
    subsetWithElement.add(element);
    powerSetSubSetWithElement.add(subsetWithElement);
}

Если мы объединим все фрагменты кода, мы сможем см. наш конечный продукт:

Set<Set<T>> powerSet = new HashSet<>();
powerSet.addAll(powerSetSubSetWithoutElement);
powerSet.addAll(powerSetSubSetWithElement);

4.3. Примечания для модульных тестов

public Set<Set<T>> recursivePowerSet(Set<T> set) {
    if (set.isEmpty()) {
        Set<Set<T>> ret = new HashSet<>();
        ret.add(set);
        return ret;
    }

    T element = set.iterator().next();
    Set<T> subSetWithoutElement = getSubSetWithoutElement(set, element);
    Set<Set<T>> powerSetSubSetWithoutElement = recursivePowerSet(subSetWithoutElement);
    Set<Set<T>> powerSetSubSetWithElement = addElementToAll(powerSetSubSetWithoutElement, element);

    Set<Set<T>> powerSet = new HashSet<>();
    powerSet.addAll(powerSetSubSetWithoutElement);
    powerSet.addAll(powerSetSubSetWithElement);
    return powerSet;
}

Теперь давайте проверим. У нас есть несколько критериев для подтверждения:

Во-первых, мы проверяем размер набора мощности, и он должен быть 2n для набора размера n. Тогда каждый элемент будет встречаться только один раз в подмножестве и 2n-1 разных подмножествах. Наконец, каждое подмножество должно появиться один раз.

Если все эти условия соблюдены, мы можем быть уверены, что наша функция работает. Теперь, поскольку мы использовали Set\u003cSet\u003e, мы уже знаем, что повторений нет. В этом случае нам нужно только проверить размер набора мощности и количество вхождений каждого элемента в подмножествах.

Чтобы проверить размер набора мощности, мы можем использовать:

И чтобы проверить количество вхождений каждого элемента:

MatcherAssert.assertThat(powerSet, IsCollectionWithSize.hasSize((1 << set.size())));

Наконец, можем ли мы собрать все вместе в один модульный тест :

Map<String, Integer> counter = new HashMap<>();
for (Set<String> subset : powerSet) { 
    for (String name : subset) {
        int num = counter.getOrDefault(name, 0);
        counter.put(name, num + 1);
    }
}
counter.forEach((k, v) -> Assertions.assertEquals((1 << (set.size() - 1)), v.intValue()));

5. Оптимизация

@Test
public void givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets() {
    Set<String> set = RandomSetOfStringGenerator.generateRandomSet();
    Set<Set<String>> powerSet = new PowerSet<String>().recursivePowerSet(set);
    MatcherAssert.assertThat(powerSet, IsCollectionWithSize.hasSize((1 << set.size())));
   
    Map<String, Integer> counter = new HashMap<>();
    for (Set<String> subset : powerSet) {
        for (String name : subset) {
            int num = counter.getOrDefault(name, 0);
            counter.put(name, num + 1);
        }
    }
    counter.forEach((k, v) -> Assertions.assertEquals((1 << (set.size() - 1)), v.intValue()));
}

В этом разделе мы попытаемся свести к минимуму пространство и уменьшить количество внутренних операций для оптимального вычисления набора мощности.

5.1. Структура данных

Как мы видим в данном подходе, нам нужно много вычитаний в рекурсивном вызове, который потребляет большое количество времени и памяти.

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

Во-первых, нам нужно присвоить возрастающее число, начиная с 0, каждому объекту в заданном наборе S, что означает, что мы работаем с упорядоченным списком чисел.

Например, для заданного множества {«ЯБЛОКО», «АПЕЛЬСИН», «МАНГО» } получаем:

«ЯБЛОКО» -\u003e 0

«АПЕЛЬСИН» -\u003e 1 ~~ ~»

««MANGO» -\u003e 2

Итак, с этого момента, вместо того, чтобы генерировать подмножества S, мы генерируем их для упорядоченного списка [0, 1, 2], и, поскольку он упорядочен, мы можем моделировать вычитания с помощью стартовый индекс.

Например, если начальный индекс равен 1, это означает, что мы генерируем набор мощностей [1,2].

Чтобы получить сопоставленный идентификатор из объекта и наоборот, мы сохраняем обе стороны сопоставления. Используя наш пример, мы храним как («MANGO» -\u003e 2), так и (2 -\u003e «MANGO»). Поскольку отображение чисел началось с нуля, поэтому для обратной карты мы можем использовать простой массив для извлечения соответствующего объекта.

Одна из возможных реализаций этой функции:

Итак, для представления подмножеств есть две хорошо известные идеи:

private Map<T, Integer> map = new HashMap<>();
private List<T> reverseMap = new ArrayList<>();

private void initializeMap(Collection<T> collection) {
    int mapId = 0;
    for (T c : collection) {
        map.put(c, mapId++);
        reverseMap.add(c);
    }
}

5.2. Представление индекса

Index representation
Binary representation

Каждое подмножество представлено индексом его значений. Например, индексное отображение заданного набора {«ЯБЛОКО», «ОРАНЖЕВЫЙ», «МАНГО»} будет следующим:

Итак, мы можем получить соответствующий набор из подмножества индексов с помощью заданное отображение:

{
   {} -> {}
   [0] -> {"APPLE"}
   [1] -> {"ORANGE"}
   [0,1] -> {"APPLE", "ORANGE"}
   [2] -> {"MANGO"}
   [0,2] -> {"APPLE", "MANGO"}
   [1,2] -> {"ORANGE", "MANGO"}
   [0,1,2] -> {"APPLE", "ORANGE", "MANGO"}
}

5.3. Двоичное представление

private Set<Set<T>> unMapIndex(Set<Set<Integer>> sets) {
    Set<Set<T>> ret = new HashSet<>();
    for (Set<Integer> s : sets) {
        HashSet<T> subset = new HashSet<>();
        for (Integer i : s) {
            subset.add(reverseMap.get(i));
        }
        ret.add(subset);
    }
    return ret;
}

Или мы можем представить каждое подмножество в двоичном виде. Если элемент фактического набора существует в этом подмножестве, его соответствующее значение равно 1; в противном случае это 0.

Для нашего примера с фруктами набор мощности будет:

Итак, мы можем получить соответствующий набор из двоичного подмножества с заданным отображением:

{
    [0,0,0] -> {}
    [1,0,0] -> {"APPLE"}
    [0,1,0] -> {"ORANGE"}
    [1,1,0] -> {"APPLE", "ORANGE"}
    [0,0,1] -> {"MANGO"}
    [1,0,1] -> {"APPLE", "MANGO"}
    [0,1,1] -> {"ORANGE", "MANGO"}
    [1,1,1] -> {"APPLE", "ORANGE", "MANGO"}
}

5.4. Реализация рекурсивного алгоритма

private Set<Set<T>> unMapBinary(Collection<List<Boolean>> sets) {
    Set<Set<T>> ret = new HashSet<>();
    for (List<Boolean> s : sets) {
        HashSet<T> subset = new HashSet<>();
        for (int i = 0; i < s.size(); i++) {
            if (s.get(i)) {
                subset.add(reverseMap.get(i));
            }
        }
        ret.add(subset);
    }
    return ret;
}

На этом шаге мы попытаемся реализовать предыдущий код, используя обе структуры данных.

Перед вызовом одной из этих функций нам нужно вызвать метод initializeMap, чтобы получить упорядоченный список. Кроме того, после создания нашей структуры данных нам нужно вызвать соответствующую функцию unMap для извлечения фактических объектов:

Итак, давайте попробуем свои силы в представлении индекса:

public Set<Set<T>> recursivePowerSetIndexRepresentation(Collection<T> set) {
    initializeMap(set);
    Set<Set<Integer>> powerSetIndices = recursivePowerSetIndexRepresentation(0, set.size());
    return unMapIndex(powerSetIndices);
}

Теперь давайте посмотрим на бинарный подход:

private Set<Set<Integer>> recursivePowerSetIndexRepresentation(int idx, int n) {
    if (idx == n) {
        Set<Set<Integer>> empty = new HashSet<>();
        empty.add(new HashSet<>());
        return empty;
    }
    Set<Set<Integer>> powerSetSubset = recursivePowerSetIndexRepresentation(idx + 1, n);
    Set<Set<Integer>> powerSet = new HashSet<>(powerSetSubset);
    for (Set<Integer> s : powerSetSubset) {
        HashSet<Integer> subSetIdxInclusive = new HashSet<>(s);
        subSetIdxInclusive.add(idx);
        powerSet.add(subSetIdxInclusive);
    }
    return powerSet;
}

5.5. Итерировать через [0, 2n)

private Set<List<Boolean>> recursivePowerSetBinaryRepresentation(int idx, int n) {
    if (idx == n) {
        Set<List<Boolean>> powerSetOfEmptySet = new HashSet<>();
        powerSetOfEmptySet.add(Arrays.asList(new Boolean[n]));
        return powerSetOfEmptySet;
    }
    Set<List<Boolean>> powerSetSubset = recursivePowerSetBinaryRepresentation(idx + 1, n);
    Set<List<Boolean>> powerSet = new HashSet<>();
    for (List<Boolean> s : powerSetSubset) {
        List<Boolean> subSetIdxExclusive = new ArrayList<>(s);
        subSetIdxExclusive.set(idx, false);
        powerSet.add(subSetIdxExclusive);
        List<Boolean> subSetIdxInclusive = new ArrayList<>(s);
        subSetIdxInclusive.set(idx, true);
        powerSet.add(subSetIdxInclusive);
    }
    return powerSet;
}

Теперь есть хорошая оптимизация, которую мы можем сделать с двоичным представлением. Если мы посмотрим на это, мы увидим, что каждая строка эквивалентна двоичному формату числа в [0, 2n).

Итак, если мы перебираем числа от 0 до 2n, мы можем преобразовать этот индекс в двоичный и использовать его для создания логического представления каждого подмножества:

5.6. Подмножества минимального изменения с помощью кода Грея

private List<List<Boolean>> iterativePowerSetByLoopOverNumbers(int n) {
    List<List<Boolean>> powerSet = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) {
        List<Boolean> subset = new ArrayList<>(n);
        for (int j = 0; j < n; j++)
            subset.add(((1 << j) & i) > 0);
        powerSet.add(subset);
    }
    return powerSet;
}

Теперь, если мы определим любую биективную функцию от двоичного представления длины n до числа в [0, 2n), мы можем генерировать подмножества в любом порядке, который мы хотим.

Код Грея — это хорошо известная функция, которая используется для генерации двоичных представлений чисел таким образом, чтобы двоичное представление последовательных чисел отличалось только одним битом (даже разница между последним и первым числом равна единице).

Таким образом, мы можем оптимизировать это еще немного:

6. Отложенная загрузка

private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(int n) {
    List<List<Boolean>> powerSet = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) {
        List<Boolean> subset = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            int grayEquivalent = i ^ (i >> 1);
            subset.add(((1 << j) & grayEquivalent) > 0);
        }
        powerSet.add(subset);
    }
    return powerSet;
}

Чтобы минимизировать использование пространства набора мощности, что составляет O(2n), мы можем использовать интерфейс Iterator для выборки каждое подмножество, а также каждый элемент в каждом подмножестве лениво.

6.1. ListIterator

Во-первых, чтобы иметь возможность выполнять итерацию от 0 до 2n, у нас должен быть специальный итератор, который перебирает этот диапазон, но не использует весь диапазон заранее.

Чтобы решить эту проблему, мы будем использовать две переменные; один для размера, который равен 2n, а другой для текущего индекса подмножества. Наша функция hasNext() проверит, что позиция меньше размера:

А наша функция next() возвращает подмножество для текущей позиции и увеличивает значение позиции на единицу:

abstract class ListIterator<K> implements Iterator<K> {
    protected int position = 0;
    private int size;
    public ListIterator(int size) {
        this.size = size;
    }
    @Override
    public boolean hasNext() {
        return position < size;
    }
}

6.2. Subset

@Override
public Set<E> next() {
    return new Subset<>(map, reverseMap, position++);
}

Чтобы получить Subset с ленивой загрузкой, мы определяем класс, расширяющий AbstractSet, и переопределяем некоторые из его функций.

Перебирая все биты, равные 1, в принимающей маске (или позиции) подмножества, мы можем реализовать итератор и другие методы в AbstractSet.

Например, size() — это количество единиц в принимающей маске:

А функция contains() определяет, равен ли соответствующий бит в маске единице или нет:

@Override
public int size() { 
    return Integer.bitCount(mask);
}

~ ~~»

@Override
public boolean contains(@Nullable Object o) {
    Integer index = map.get(o);
    return index != null && (mask & (1 << index)) != 0;
}

«Мы используем еще одну переменную — restSetBits — для изменения ее всякий раз, когда мы извлекаем соответствующий элемент в подмножестве, мы изменяем этот бит на 0. Затем функция hasNext() проверяет, не равно ли остаточное значение SetBits нулю (то есть имеет по крайней мере один бит со значением 1):

@Override
public boolean hasNext() {
    return remainingSetBits != 0;
}

А функция next() использует самую правую 1 из оставшихся SetBits, затем преобразует ее в 0, а также возвращает соответствующий элемент:

@Override
public E next() {
    int index = Integer.numberOfTrailingZeros(remainingSetBits);
    if (index == 32) {
        throw new NoSuchElementException();
    }
    remainingSetBits &= ~(1 << index);
    return reverseMap.get(index);
}

6.3. PowerSet

Чтобы иметь класс PowerSet с отложенной загрузкой, нам нужен класс, расширяющий AbstractSet\u003cSet\u003cT\u003e\u003e.

Функция size() просто равна 2 в степени размера набора:

@Override
public int size() {
    return (1 << this.set.size());
}

Поскольку набор мощности будет содержать все возможные подмножества входного набора, функция contains(Object o) проверяет, все ли элементы объекта o существуют в reverseMap (или во входном наборе):

@Override
public boolean contains(@Nullable Object obj) {
    if (obj instanceof Set) {
        Set<?> set = (Set<?>) obj;
        return reverseMap.containsAll(set);
    }
    return false;
}

Чтобы проверить равенство данного объекта с этим классом, мы можем только проверить, равен ли входной набор данному объекту: ~ ~~

@Override
public boolean equals(@Nullable Object obj) {
    if (obj instanceof PowerSet) {
        PowerSet<?> that = (PowerSet<?>) obj;
        return set.equals(that.set);
    }
    return super.equals(obj);
}

Функция iterator() возвращает экземпляр ListIterator, который мы уже определили:

@Override
public Iterator<Set<E>> iterator() {
    return new ListIterator<Set<E>>(this.size()) {
        @Override
        public Set<E> next() {
            return new Subset<>(map, reverseMap, position++);
        }
    };
}

Библиотека Guava использует эту идею ленивой загрузки, и эти PowerSet и Subset являются эквивалентными реализациями библиотеки Guava.

Для получения дополнительной информации проверьте их исходный код и документацию.

Кроме того, если мы хотим выполнить параллельную операцию над подмножествами в PowerSet, мы можем вызывать Subset для разных значений в ThreadPool.

7. Резюме

Подводя итог, сперва мы изучили, что такое степенное множество. Затем мы сгенерировали его с помощью библиотеки Guava. После этого мы изучили подход и то, как его реализовать, а также как написать для него юнит-тест.

Наконец, мы использовали интерфейс Iterator для оптимизации пространства генерации подмножеств, а также их внутренних элементов.

Как всегда, исходный код доступен на GitHub.

«Получение мощного набора набора в Java»

Spring на русском

«Получение мощного набора набора в Java»

«1. Введение

2. Определение набора мощности

3. Библиотека Guava

4. Подход к генерации набора мощности

4.1. Алгоритм

Итак, во-первых, давайте напишем код Java для извлечения одного элемента и получения оставшихся подмножеств:

Теперь давайте проверим. У нас есть несколько критериев для подтверждения:

В этом разделе мы попытаемся свести к минимуму пространство и уменьшить количество внутренних операций для оптимального вычисления набора мощности.

Как мы видим в данном подходе, нам нужно много вычитаний в рекурсивном вызове, который потребляет большое количество времени и памяти.

Каждое подмножество представлено индексом его значений. Например, индексное отображение заданного набора {«ЯБЛОКО», «ОРАНЖЕВЫЙ», «МАНГО»} будет следующим:

На этом шаге мы попытаемся реализовать предыдущий код, используя обе структуры данных.

Чтобы получить Subset с ленивой загрузкой, мы определяем класс, расширяющий AbstractSet, и переопределяем некоторые из его функций.

6.3. PowerSet

7. Резюме

Добавить комментарий Отменить ответ