Набор мощности входного набора как пользовательской коллекции

Я читал книгу «Эффективная Java», и я застрял в этом коде. Я не могу понять, как этот код генерирует набор мощности.

Код:

public class PowerSet {

    public static final <E> Collection<Set<E>> of(Set<E> s) {
        List<E> src = new ArrayList<>(s);
        if (src.size() >= 30)
            throw new IllegalArgumentException("Set too big " + s);
        return new AbstractList<Set<E>>() {

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

            @Override
            public boolean contains(Object o) {
                return o instanceof Set && src.containsAll((Set) o);
            }

            @Override
            public Set<E> get(int index) {
                Set<E> result = new HashSet<>();
                for (int i = 0; index != 0; i++, index >>= 1)
                    if ((index & 1) == 1)
                        result.add(src.get(i));
                return result;
            }
        };
    }

    public static void main(String[] args) {
        Collection<Set<String>> result = of(Set.of("a", "b", "c"));
        System.out.println(result);
    }
}

Вывод:

[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]

Может кто-нибудь объяснить, как этот код генерирует powerset данного набора.


person deadshot    schedule 24.07.2020    source источник
comment
С чем именно вы боретесь? Помогает ли это stackoverflow.com/a/24366172/1398418?   -  person Oleg    schedule 24.07.2020


Ответы (1)


Код использует двоичное представление номера индекса в качестве карты того, какой элемент s нужно включить.

Например, предполагая только 3 бита в числе:

index   | a | b | c
--------------------
0 (000) | 0 | 0 | 0 -> take nothing
1 (001) | 0 | 0 | 1 -> take only c
2 (010) | 0 | 1 | 0 -> take only b
3 (011) | 0 | 1 | 1 -> take a and b
4 (100) | 1 | 0 | 0 -> take only a
...

Метод get сгенерированного списка следует этой логике с заданным входом index:

  • index >>= 1 сдвигает все биты на одну позицию вправо с каждым циклом
  • (index & 1) == 1 проверяет, равен ли самый правый бит index 1

Оператор & является двоичным И, поэтому 2 и 1 равняется двоичному 010 AND 001, что дает 000 (не равно 1 или 001), а 3 и 1 равняется двоичному 011 AND 001, что дает 001 (равно 1 или 001)

  • Если это оценивается как true, i-й элемент добавляется в список.
  • Это заканчивается, когда index == 0, т.е. больше нет битов для сдвига / элементов для добавления

Пример для индекса = 3:

i | index | (index & 1) == 1 | element added
---------------------------------------------
0 |   011 |             TRUE |   a (0-th element)
1 |   001 |             TRUE |   b (1-th element)
2 |   000 |            FALSE |   - 
(terminates as index == 0)
person tb189    schedule 24.07.2020