0 또는 0이되는 정수 배열의 가장 큰 하위 집합을 찾으려면 어떻게합니까

Question

배열의 가장 큰 하위 집합 인 [0,1,4,5,6,8]은 xors가 0이 [0 , 1,4,5] 0^1^4^5 = 0 (여기서 ^는 xor이다). 나는 이것이 무차별 한 힘에 의해 기하 급수적으로 행해질 수 있다는 것을 알고 있지만, 나는 하한이 무엇인지, 그리고 그 시간에 어떤 알고리즘이 그것을 해결하는지 알고 싶다.

Rational sieve 알고리즘을 구현하려고합니다. wikipedia article 너머에는 알고리즘에 대한 리소스가 거의 없습니다. 합리적인 체를 완성하려면 배열 그룹의 하위 집합을 찾으십시오. 즉, 해당 요소를 더할 때 결과 배열의 수가 짝수가되도록 배열의 그룹을 찾습니다. 예 :

[2,3,4,5] + [4,3,4,3] = [6,6,8,8] 이러한 배열은 큰 세트.

위키 피 디아의 기사에 따르면, 이것은 선형 대수학을 사용하여 해결할 수 있지만이를 해결하기에 충분한 선형 대수학을 알지 못합니다.

알고리즘의 목적 상, 빈 부분 집합은 유용하지 않습니다.

나는 배열에 0과 1만을 가질 수 있으며 배열을 단일 숫자로 두어 합계를 단일 연산자로 계산할 수 있다고 말함으로써 문제를 단순화했다. 그렇지 않으면 동일한 문제가된다.

Answer 1

예, 선형 최적화 문제로 공식화 할 수 있습니다. 정수가 k 비트되었다고 가정하고 그 n 거기에는 컬럼은 정수를 나타내는 사용 k * n 매트릭스 A,로 나타낼 수 및 열 n의 r 정수 i의 r 번째 비트 인 행.

그런 다음 정수의 선택 및 제거는 A * x으로 표시 할 수 있습니다. 여기서 x은 선택한 정수의 위치에 1을 갖는 n 크기의 벡터입니다. 이것은 GF (2)를 넘어야하므로 곱셈이 표준이고 덧셈은 XOR입니다. 따라서 Ax = 0에 해당하는 maximize(|x|)을 해결하고 있습니다.