生成两两汉明距离为d的二进制向量：理论与高效实现问询

你正在尝试生成n个长度为l的二进制向量，要求任意两个向量间的汉明距离恰好为偶数d，目前遇到了随机搜索效率低、不清楚参数约束的问题。下面我来拆解这两个核心问题：

一、n、l、d之间的理论约束 #

这属于二元等距码的研究范畴，这类码的任意两个码字汉明距离都相等。针对你要求d为偶数的情况，关键约束如下：

• 必要可行性条件：设d=2t（t为正整数），则必须满足 (n-1)*t ≤ l。
  这个推导来自：每个后续向量与基准向量有2t个位置不同，任意两个后续向量的差异区域需要恰好重叠t个位置（这样它们之间的汉明距离才会是2t），所有这些重叠区域的总规模不能超过向量总长度l。如果不满足这个条件，根本不存在符合要求的向量集。
• 存在性保障：只要满足上述条件，基本都能构造出符合要求的向量集。比如当l是t的倍数、n-1是l/t的因数时，构造会非常直观。

二、高效实现方案 #

你的随机搜索方案效率极低，尤其是l和n增大时，几乎无法在合理时间内得到结果。这里提供两种确定性构造的思路，彻底避免随机搜索的弊端：

方法1：固定差异区域构造法 #

这是最直观的构造方式，核心逻辑是：

1. 先选一个基准向量（比如全1或全0）。
2. 后续每个向量与基准向量在2t个位置不同，且任意两个向量的差异区域恰好重叠t个位置（保证它们之间的汉明距离为d=2t）。

对应的Python实现代码：

import numpy as np
from itertools import combinations

def generate_equidistant_codes(l, n, d):
    if d % 2 != 0:
        raise ValueError("要求d为偶数，请输入合法的d值")
    t = d // 2
    # 先做可行性检查，避免无效构造
    if (n-1)*t > l:
        raise ValueError(f"无法构造{l}长度、{n}个向量且汉明距离为{d}的集合：(n-1)*t = {(n-1)*t} > l = {l}")
    
    # 基准向量：全1
    codebook = [np.ones(l, dtype=int)]
    # 固定t个位置作为公共差异区，剩下的位置分组生成差异区
    fixed_pos = list(range(t))
    remaining_pos = list(range(t, l))
    
    # 从剩余位置中选t个的组合，和固定位置一起构成翻转区域
    for comb in combinations(remaining_pos, t):
        if len(codebook) >= n:
            break
        new_code = codebook[0].copy()
        flip_pos = fixed_pos + list(comb)
        new_code[flip_pos] = 1 - new_code[flip_pos]
        codebook.append(new_code)
    
    # 如果组合数不够，用轮换翻转区域的方式补全
    while len(codebook) < n:
        current = codebook[-1].copy()
        # 选t个已翻转的位置和t个未翻转的位置进行翻转
        flipped = set(np.where(current != codebook[0])[0])
        if len(flipped) < t:
            # 初始阶段全选未翻转的位置
            to_flip = np.random.choice([i for i in range(l) if i not in flipped], 2*t, replace=False)
        else:
            flip_old = np.random.choice(list(flipped), t, replace=False)
            flip_new = np.random.choice([i for i in range(l) if i not in flipped], t, replace=False)
            to_flip = np.concatenate([flip_old, flip_new])
        current[to_flip] = 1 - current[to_flip]
        codebook.append(current)
    
    return np.array(codebook)

方法2：线性码构造法 #

如果需要更大规模的向量集，可以利用二元线性码的特性，比如Reed-Muller码的子类，或者基于有限域的构造。不过对于大多数实用场景，方法1已经足够高效且容易理解。

三、原代码的问题分析 #

你的随机搜索方案存在两个核心问题：

1. 无可行性检查：当(n-1)*t > l时，根本不存在符合要求的向量集，代码会陷入无限循环。
2. 效率极低：随机生成符合条件的向量概率极低，尤其是l较大时，大量无效尝试会导致代码长时间停滞。

示例验证 #

调用generate_equidistant_codes(4, 3, 2)，会得到类似如下结果：

[[1 1 1 1]
 [0 0 1 1]
 [0 1 0 1]]

任意两个向量之间的汉明距离都是2，完全符合要求。

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