求Python实现GF(2)上向量组所有线性组合的递归方法

你原代码的核心问题是没理解GF(2)线性组合的本质：GF(2)中每个向量的系数只能是0或1，所以所有线性组合等价于所有可能的向量子集的和（选0个向量得到零向量，选1个得到单个向量，选多个则是它们的GF(2)加法结果）。

递归的思路其实很简单：把大问题拆成小问题——要计算列表L的span，我们可以分成两种情况：

• 不包含L最后一个向量的所有组合：即L去掉最后一个向量后的span
• 包含L最后一个向量的所有组合：即L去掉最后一个向量后的span里的每个向量，都和最后一个向量做GF(2)加法得到的结果
  把这两部分合并，就是L的所有线性组合。

首先需要一个GF(2)向量加法的辅助函数（假设向量用字典存储，键为标签集合D中的元素，值为0或1）：

def gf2_add(v1, v2, D):
    # GF(2)加法：对应标签的值相加模2，等价于异或
    result = {}
    for label in D:
        val1 = v1.get(label, 0)
        val2 = v2.get(label, 0)
        result[label] = (val1 + val2) % 2
    return result

然后是递归实现的GF2_span函数：

def GF2_span(D, L):
    # Base Case：空列表的span只有零向量
    if not L:
        zero_vec = {label: 0 for label in D}
        return [zero_vec]
    
    # 递归处理去掉最后一个向量的子列表
    last_vec = L[-1]
    span_rest = GF2_span(D, L[:-1])
    
    # 生成包含最后一个向量的所有组合：子span的每个向量加上last_vec
    span_with_last = [gf2_add(vec, last_vec, D) for vec in span_rest]
    
    # 合并两部分结果
    return span_rest + span_with_last

1. Base Case处理：当输入的向量列表L为空时，唯一的线性组合是零向量（所有标签对应值为0），直接返回包含该向量的列表。
2. 递归分解：取L的最后一个向量，递归计算去掉该向量后的子列表的span，得到所有不包含最后一个向量的组合。
3. 生成包含最后一个向量的组合：将子span中的每个向量与最后一个向量做GF(2)加法，得到所有包含最后一个向量的组合。
4. 合并结果：把两种情况的组合合并，就是L的所有线性组合。

比如输入：

D = {'x', 'y'}
L = [{'x':1, 'y':0}, {'x':0, 'y':1}]
print(GF2_span(D, L))

输出会是所有4种可能的线性组合：

[
 {'x': 0, 'y': 0},
 {'x': 1, 'y': 0},
 {'x': 0, 'y': 1},
 {'x': 1, 'y': 1}
]

空列表测试：

print(GF2_span(D, []))
# 输出：[{'x': 0, 'y': 0}]

如果觉得递归难理解，也可以用迭代方式生成所有系数组合（每个系数为0或1），再计算对应组合的和：

def GF2_span_iterative(D, L):
    n = len(L)
    span = []
    # 生成所有2^n种0/1系数组合（用二进制数表示）
    for i in range(2 ** n):
        # 把整数i转成n位二进制字符串，每个字符对应一个系数
        coeff_str = bin(i)[2:].zfill(n)
        coeffs = [int(c) for c in coeff_str]
        
        # 初始化结果为零向量
        result = {label: 0 for label in D}
        for coeff, vec in zip(coeffs, L):
            if coeff == 1:
                result = gf2_add(result, vec, D)
        span.append(result)
    return span

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