Подсчитать количество подмножеств, имеющих совокупное значение XOR меньше k

Question

При заданном наборе чисел S размера N. Количество всех подмножеств S, у которых есть совокупное XOR элементов подмножества, меньше, чем K.

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

Example: 
S = {1,2}
K = 4
U = {{},{1},{2},{1,2}}
Answer is 4 As 
cumulative XOR values are 0 for {}, 1 for {1}, 2 for {2}, 3 for {1,2}.

Answer 1

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

• Как вы указали, если N достаточно мало, пробуя все возможные подмножества в O(2^N), вы получитеожидаемый результат.
• Если значения в S ограничены каким-либо достаточно малым значением, вы можете использовать решение динамического программирования, изложенное в посте мастера.
• Если и N высокое, и значенияв S большие (миллиарды и выше), есть более сложный, но полиномиальный подход, который вы можете применить.Схема выглядит следующим образом:

Давайте посмотрим на двоичные представления чисел в S, например для чисел 17, 5, 20, 14 это будет:

10001 17
00101  5
10100 20
01110 14

И то же самое для K, например, давайте возьмем K = 11: 01011 11

Если бы мы хотели посчитать, сколько подмножеств XOR в точно K, мы могли бы представить проблему как системулинейные уравнения по модулю 2, с таким количеством переменных, как число в S, и таким же количеством уравнений, сколько в наших числах значащих бит.Более конкретно, пусть i-ое уравнение представляет ограничение «XOR i-го бита чисел в подмножестве S должно быть равно i-му биту в K».(Обратите внимание, что операция XOR эквивалентна сумме по модулю 2).Например, для наименьшего (самого правого) бита мы имеем следующее: x1 * 1 + x2 * 1 + x3 * 0 + x4 * 0 = 1 (mod 2), где x_j равен 0 или 1, в зависимости от того, добавляем мы j-тое число в наше подмножество или нет.

Обратите внимание, что эта система уравнений может иметь 0, 1 или много решений.В случае многих решений каждая из независимых переменных может принимать либо 0, либо 1, и, таким образом, число решений составляет 2 ^ (независимые переменные).

Мы можем определить количество независимых переменных и разрешимостьсистемы линейных уравнений с использованием исключения Гаусса, которая выполняется в O(n^3) для квадратной матрицы размером n - в вашем случае матрица не квадратная, поэтому мы можем использовать большее из (|S|, log(max(S)) для оценки сложности.

Отлично, теперь мы можем пройти все K 'от 0 до K-1, решить задачу отдельно и суммировать результаты.Тем не менее, это нигде не лучше, чем решение для динамического программирования и является лишь псевдополиномом во время выполнения.Давайте сделаем еще одно наблюдение, которое приведет к полиномиальному решению: нас интересуют только O(logK) различные системы уравнений, чтобы вычислить, сколько подмножеств XOR меньше K.

Обозначим старший ненулевой битПоложение в K как B. Если все биты выше B и бит B равны 0 в XOR подмножества, которое мы берем, то, очевидно, оно будет меньше K.Таким образом, наша первая система уравнений может быть записана только для вышеупомянутых битов и игнорировать все, что ниже B.

Теперь давайте посмотрим, что произойдет, если мы допустим, чтобы B-й бит был равен 1. Если в числеK есть один или несколько нулевых битов после B-й позиции, все они также должны быть 0 в результирующем XOR.Если первый последующий ненулевой бит B2 установлен в 0 в нашем XOR, то он будет меньше K. Мы можем закодировать это наблюдение как вторую систему уравнений, сказав, что «все биты выше B равны 0, бит B равен1, все биты между B и B2 равны 0, бит B2 равен 0 "и вычисляет количество решений для него.

Если мы продолжим так до самой маленькой двоичной позиции в K, нам понадобитсяпостроить не более logK систем уравнений и получить желаемый результат.

Сложность этого подхода примерно такая же, как O(logK * max(n, logK)^3), хотя в зависимости от реализации исключение Гаусса может работать гораздо быстрее для неквадратныхматрицы.

Answer 2

Проблема очень похожа на количество подмножеств, имеющих сумму, равную k .Мы можем действовать аналогичным образом и суммировать количество подмножеств, имеющих сумму от 0 до k.

Ниже приведена моя реализация на python для того же самого.

Он использует динамическое программирование для хранения промежуточных результатов в каждой ячейке таблицы DP.Ячейка dp [i] [j] содержит количество подмножеств, равное j, которое может быть сформировано с использованием первых ith чисел в отсортированном массиве.

Сложность времени O(n * maxXor)где maxXor является maximum value which can be achieved by xoring any of the numbers in the array.Максимальное значение maxXor будет равно наименьшей мощности 2, превышающей maxValue present in array и K

from math import floor, log


arr = [1, 2]
K = 4


def getCoundDp(arr, k):
    arr.sort()
    maxVal = arr[-1]
    maxXor = 2**(floor(log(max(maxVal, k), 2)) + 1)
    dp = [[0 for i in range(maxXor)] for a in arr]
    dp[0][0] = 1
    # in the 1st row, mark the arr[0] to have count 1
    dp[0][arr[0]] = 1
    for row in range(1, len(arr)):
        for col in range(maxXor):
            dp[row][col] += dp[row-1][col]
            neededXor = col ^ arr[row]
            dp[row][col] += dp[row-1][neededXor]
    return sum(dp[-1][:k])


print(getCoundDp(arr, K))

Ваше предложение создания и проверки всех подмножеств будет очень медленным O(2^n).Но все же должно быть ценным, по крайней мере, для проверки более быстрых реализаций.Ниже приведен пример метода грубой силы в Python с использованием itertools.combination Подробнее об этом можно прочитать здесь .

from itertools import combinations


def getXor(arr):
    xor = 0
    for i in arr:
        xor ^= i
    return xor


def getCountBruteForce(arr, k):
    arr.sort()
    countLessThanK = 0
    for r in range(0, len(arr)+1):
        for comb in combinations(arr, r):
            xor = getXor(comb)
            if xor < k:
                countLessThanK += 1
    return(countLessThanK)