Дано множество V, и для каждого элемента v в V существует подмножество N (v), где v находится в N (v). Затем я хочу вычислить значение a (X) для каждого подмножества X из V. Я делаю это рекурсивно с базовым самым большим подмножеством a (V) = 0, а затем рекурсивно нахожу значения других подмножеств от большого до малого, потому что рекурсивная функция, которая вычисляет a (X), требует больших подмножеств значений: рекурсивная функция
Есть 2 сложности:
- есть много подмножеств: 2 ^ | V |, поэтому работа со словарем будет очень потреблять память (верно?) . Я предпочитаю список с простым отображением индексов списка на подмножества. Это можно сделать, преобразовав подмножества в двоичное целое число: subset {v1, v2, v6}, где | V | 7 будет индексом 0100011 = 35.
- Мне нужно l oop по подмножествам от большого до малого, поэтому от двоичных целых чисел с большим количеством единиц к числам с меньшим количеством единиц. Вот где я застрял, потому что понятия не имею, как это сделать (эффективно). побитовый оператор '|' Я могу эффективно вычислить «пересечение» подмножеств: 1100 | 1001 = 1101 или 12 | 9 = 13.
Мой код будет выглядеть примерно так:
a[|V|^2]=0 #(this is 11111111111111 in binary, so the biggest subset)
Loop in decreasing size of subsets: #dont know how to do this :(
pick vertex v that is not in X, and denote it in binary (v3 becomes 000000000100)
a[X] = a[X | v] + a[X | N[v]] + 1
Итак, мой вопрос сводится к следующему: как мне пройти через oop через список в порядке количества единиц в их двоичном индексе? Или, есть ли совершенно другой способ вычислить значения a (X) для каждого подмножества X из V? Спасибо за чтение, Joost