Поиск N элементов в массиве whoes xor равен P

Я работаю над проблемой, в которой я ожидаю найти количество комбинаций элементов N<20 в массиве, XOR которого равно P.

Например: наш массив {2 4 5 2 7}

1), если N = 2 и P = 6,

Ответ равен 2 (так как мы можем выбрать только (2 xor 4) = 6 и (4 xor 2) = 6)

{ 2 4 5 2 7} или {2 4 5 2 7}

2), если N = 3 и P = 6

Ответ: 1 ((4 xor 5 xor 7) = 6)

Размер массива может быть действительно огромным (примерно 10 ^ 6), поэтому я ищу быстрый алгоритм для решения этой проблемы.

Ответ 1

EDIT не работает, потому что N фиксировано

Используя линейную алгебру:

Как было предложено @blazs, вы можете просматривать P и каждый номер вашего массива в виде векторов в векторном пространстве Z/2Z. Что еще, поскольку XOR ассоциативно и коммутативно, вы не ищете комбинации элементов вашего массива, но наборы этих элементов, а набор также может быть закодирован как вектор Z/2Z.

Итак, вы получите матричное уравнение, такое как M * S = P, где P - xor-sum в векторном формате Z/2Z, M - это матрица, столбцы которой являются элементами массива в Z/2Z формат, а S - неизвестное уравнение.

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

Ответ 2

Предлагаемый рекурсивный алгоритм может быть быстрее, чем грубая сила:

Найдите бит P, который равен 1. Любая комбинация решений должна содержать по крайней мере одно число, которое имеет 1 в этом бите.

Для каждого элемента K массива, который имеет 1 в этом бите, повторяется с:

P '= P xor K (xor - substraction)
arr '= arr - {набор J в arr, который имеет 1 в этом бите и какой индекс меньше или равен K} (поскольку мы предполагаем, что K является первым элементом комбинации с 1 в этом положении в пространстве решений)
N = N - 1

Случаи прекращения:

если P = 0 и N = 0, одно решение
если N = 0 и P!= 0, никакого решения
если arr пуст, нет решения
если там бит, где P имеет 1 и ни один элемент из arr, нет решения

Обратите внимание, что XOR ассоциативен и коммутативен, поэтому мы подсчитываем множества, а не комбинации.