求数组子集异或值与给定整数N的最大异或值（Python优化解法）

给定整数数组P，定义函数F(M)返回子集M中所有整数的异或值（空集时F(M)=0）。需要找出表达式 N XOR F(M) 的最大值，其中M是P的任意子集，N是给定的≤1000的整数。

示例输入 #

• N = 4
• P = [1, 2, 3]
• 数组元素个数 = 3

示例输出 #

7

约束条件 #

• Pi ≤ 1000
• 数组元素个数 ≤ 1000
• N ≤ 1000

我之前用暴力法（时间复杂度O(2^n)）实现，但效率太低，现在需要Python语言的优化解决方案。

原暴力法代码 #

from itertools import combinations
def find_max_xor(N,P):
    # find the maximum XOR value
    comb = []

    for i in range(len(P) + 1):
        comb += [list(j) for j in combinations([1,2,3], i)]  # 注：此处存在bug，应使用P而非写死的[1,2,3]

    arr = []
    for i in comb:
        if len(i):
            res = 0
            for l in range(len(i)):
                res ^= i[l]
            arr.append(N ^ res)
    return max(arr)

n = 4
p = [1,2,3]
# numIntegers = 3
result = find_max_xor(n,p)
print("result : ", result)

核心思路 #

子集异或的所有可能值构成一个线性空间，可以用线性基（基于高斯消元思想构造）来高效枚举所有可能的异或结果，再从中找出与N异或后的最大值。该方法时间复杂度为O(n * log(max_p))，其中max_p是数组元素的最大值（此处≤1000，log₂(1000)≈10，总复杂度约10^4，远优于暴力法）。

实现步骤 #

1. 构造线性基：遍历数组P的每个元素，将其插入线性基中，确保基中元素线性无关且每个元素的最高位唯一。
2. 计算最大异或值：从线性基的最高位开始，尝试用基元素与当前结果异或，若能使结果更大则保留异或后的结果，最终得到目标最大值。

Python实现代码 #

def build_linear_basis(arr):
    # 1000的二进制最高位是第9位（从0计数），所以设置长度为10的基数组足够
    basis = [0] * 10
    for num in arr:
        if num == 0:
            continue
        curr = num
        # 从高位到低位处理
        for i in reversed(range(10)):
            if (curr >> i) & 1:
                if basis[i] == 0:
                    basis[i] = curr
                    break
                else:
                    curr ^= basis[i]
    return basis

def find_max_xor(N, basis):
    curr = N
    for i in reversed(range(10)):
        # 若异或基元素后结果更大，则更新当前值
        if basis[i] != 0 and (curr ^ basis[i]) > curr:
            curr ^= basis[i]
    return curr

# 测试示例
n = 4
p = [1, 2, 3]
basis = build_linear_basis(p)
result = find_max_xor(n, basis)
print("result : ", result)  # 输出7

代码说明 #

• build_linear_basis：通过遍历数组元素，将每个数分解到对应的二进制高位，构造出能表示所有子集异或结果的线性基。
• find_max_xor：从高位到低位遍历线性基，每次尝试用基元素优化当前异或结果，最终得到N XOR F(M)的最大值。
• 修复了原暴力法中写死组合数组的bug。

内容的提问来源于stack exchange，提问作者Niul Panvalkar