정수 배열의 하위 집합이 존재하는지 여부를 확인하는 효율적인 알고리즘은 모든 요소의 xor가 주어진 값입니까?

Question

나는 양의 정수 배열 - {1,5,8,2,10}과 주어진 값 7을 가지고있다. 배열의 하위 집합이 존재하여 그 요소의 XOR이 값 7 이 경우 5 xor 2가 7이므로 하위 집합은 {5,2}입니다. 하나의 순진한 해법은 모든 하위 집합을 찾고 해가 존재하는지 확인하는 것입니다. 순진한 알고리즘보다 나은 알고리즘을 원합니다. 참고 : - 해결책이 있는지 여부 만 확인하면됩니다. 하위 집합을 찾을 필요가 없습니다.

Answer 1

이것은 두 개의 요소 (GF (2))가있는 유한 필드에서 선형 방정식 시스템을 해결하는 것으로 요약됩니다. 여기서 비트 단위 XOR은 두 벡터를 더하는 것과 같습니다. 샘플 입력은 이와 같이 벡터에 해당합니다.

1: 0001 
5: 0101 
8: 1000 
2: 0010 
10: 1010 
7: 0111 

시스템은 다음과 같습니다.

[0 0 1 0 1] [a] [0] 
[0 1 0 0 0] [b] [1] 
[0 0 0 1 1] [c] = [1] 
[1 1 0 0 0] [d] [1] 
       [e] 

다음 파이썬 코드는 Gaussian elimination을 사용하며 비트 연산을 사용하여 구현됩니다. 고정 너비 정수의 경우 선형 시간으로 실행됩니다. 이미 인터넷에서 수백만 건의 치료법이있는 경우 가우스 제거를 재검토하지 않은 것에 대해 용서해주십시오.

#!/usr/bin/env python3 
def least_bit_set(x): 
    return x & (-x) 


def delete_zeros_from(values, start): 
    i = start 
    for j in range(start, len(values)): 
     if values[j] != 0: 
      values[i] = values[j] 
      i += 1 
    del values[i:] 


def eliminate(values): 
    values = list(values) 
    i = 0 
    while True: 
     delete_zeros_from(values, i) 
     if i >= len(values): 
      return values 
     j = i 
     for k in range(i + 1, len(values)): 
      if least_bit_set(values[k]) < least_bit_set(values[j]): 
       j = k 
     values[i], values[j] = (values[j], values[i]) 
     for k in range(i + 1, len(values)): 
      if least_bit_set(values[k]) == least_bit_set(values[i]): 
       values[k] ^= values[i] 
     i += 1 


def in_span(x, eliminated_values): 
    for y in eliminated_values: 
     if least_bit_set(y) & x != 0: 
      x ^= y 
    return x == 0 


def main(): 
    values = [1, 5, 8, 2, 10] 
    eliminated_values = eliminate(values) 
    print(eliminated_values) 
    x = int(input()) 
    print(in_span(x, eliminated_values)) 


if __name__ == '__main__': 
    main()