Нахождение подмножества, которое удовлетворяет определенному условию

Question

У меня есть несколько массивов чисел (каждый элемент массива может принимать только значение 0 или 1), как это

v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

Я хочу найти подмножества, чтобы при суммировании массивов результирующий массив имел отдельные элементы, кратные 2. Например, v1 + v2 + v3 дает результирующий массив 2, 2, 0, 2, 2. Полученный массив может иметь любое значение, кратное 2.

Другой пример:

v1: 1, 1, 1, 0, 1, 0
v2: 0, 0, 1, 0, 0, 0
v3: 1, 0, 0, 0, 0, 0
v4: 0, 0, 0, 1, 0, 0
v5: 1, 1, 0, 0, 1, 0
v6: 0, 0, 1, 1, 0, 0
v7: 1, 0, 1, 1, 0, 0

В этом примере v1 + v2 + v5 и v3 + v6 + v7 являются подходящими ответами.

Я имею в виду грубое решение, но я хотел проверить, есть ли более эффективный метод. Это эквивалентно проблеме суммы подмножеств?

Answer 1

Хотите найти все решения или одно?

Это может найти одно решение (и я думаю, что возможно расширить его, чтобы найти все решения).

Представляет каждый массив в виде двоичного числа.

Таким образом, v1 становится 10011, v2 становится 01001 и т. Д.

Пусть * обозначает побитовое добавление мода 2.

например.

v1*v2*v3 = 00000

Итак, наша цель - найти массивы, в которых добавление мода 2 равно нулю. Пусть u и v - любое двоичное число. Тогда u * v = 0 тогда и только тогда, когда u = v.

например.

(v1*v2)*v3 = 0
v1*v2 = 11010 = v3.

Также, если u * v = w, тогда

u*v*v = w*v, so
u*0 = w*v,
u = w*v

Таким образом, мы можем выполнить обратный поиск, начиная с 0. Предположим, что последний набор массивов содержит v. Тогда v * T = 0, где T - некоторое двоичное число. У нас T = 0 * v. Если T является одним из заданных массивов, то мы закончили. В противном случае мы продолжаем поиск, начиная с T.

Это формально описано ниже.

Каждое состояние - это двоичное число.

Пусть 0 будет начальным состоянием.

Указанные массивы являются некоторым подмножеством пространства состояний, скажем S.

Нашей целью является любой элемент в S.

Пусть T будет требуемым подмножеством массивов, сумма которых равна 0.

В каждом состоянии допустимы возможные действия * с любым состоянием, не входящим в T.

После каждого действия ставить массив, используемый в T.

Если S = ​​T на любом нецелевом этапе, то решения не существует.

Теперь мы можем запустить DFS в этом пространстве, чтобы найти решение.