如何找到12个两两汉明距离≥17的32位数字？算法与存在性求证

问题核心 #

需求是找到12个32位数字，使得任意两两之间的汉明距离至少为17位；更一般的问题是：找到n个32位数字，满足任意两两汉明距离≥m位。

初始采用随机选取+XOR计算汉明距离的筛选方法，但该算法效率极低，且当m=17时，代码仅能找到9个数字后陷入停滞。这里明确结论：这样的12个数字是存在的，以下是证明及优化方案。

存在性证明 #

计数论证 #

将每个32位数字视为汉明空间中的一个点，汉明距离为两点间的距离。对于任意数字x，所有与x汉明距离<17的数字数量为$\sum_{k=0}^{16} C(32,k)$，但我们只需要判断是否能放置12个两两距离≥17的点：

• 以每个点为中心、半径8（$\lfloor(17-1)/2\rfloor$）的球体，内部包含所有与中心距离≤8的数字，单个球体的大小为$\sum_{k=0}^8 C(32,k)=15033173$。
• 12个这样的球体总点数为$12×15033173=180398076$，远小于32位汉明空间的总点数$2^{32}=4294967296$，说明存在足够多的无重叠区域放置12个符合条件的数字。

构造性证明 #

可以手动构造满足条件的集合：

1. 第一个数字取全0：0x00000000
2. 第二个数字取前17位全1、后15位全0：0xFFFFF800（与0的汉明距离为17）
3. 第三个数字取中间17位全1、前后各7位和8位全0：0x007FFFF0（与前两个数字的汉明距离分别为17、30）
4. 以此类推，通过将17个连续1的块放在32位中的不同位置，可轻松构造出超过12个符合条件的数字。

随机算法低效的原因 #

当集合中已有k个数字时，新数字需要与这k个数字的汉明距离都≥17，符合条件的数字在整个空间中的占比极低：

• 单个数字的符合条件占比约为35%，但当k=9时，同时满足9个条件的占比约为$0.35^9≈0.00005$，即每20000次随机尝试才可能找到一个符合条件的数字，导致程序几乎无法继续。

更高效的解决方案 #

方法1：构造性算法（基于位扩展） #

通过扩展短码来生成满足条件的32位数字，步骤如下：

1. 先构造一组16位数字，两两汉明距离≥9；
2. 将每个16位数字扩展为32位：前16位保留原数字，后16位取原数字的16位反码。此时任意两个扩展后的数字汉明距离为原距离的2倍，即≥18，满足≥17的要求。

示例代码：

def hamming_distance(x, y):
    val = x ^ y
    dist = 0
    while val > 0:
        val &= val - 1
        dist += 1
    return dist

def construct_code(n=12, m=17):
    # 构造16位两两距离≥9的基础码
    base_codes = []
    for i in range(n):
        code = 0
        # 每个基础码包含9个连续移位的1
        for j in range(9):
            pos = (i + j) % 16
            code |= 1 << pos
        base_codes.append(code)
    
    # 扩展为32位：前16位原码，后16位反码
    result = []
    for code in base_codes:
        extended = (code << 16) | ((~code) & 0xFFFF)
        result.append(extended)
    
    # 验证
    for i in range(len(result)):
        for j in range(i+1, len(result)):
            assert hamming_distance(result[i], result[j]) >= m, f"距离不满足要求"
    return result

# 生成并输出结果
code_set = construct_code(12,17)
print("构造的12个32位数字：")
for num in code_set:
    print(hex(num))

方法2：贪心有序搜索 #

替代随机选取，按顺序遍历数字，找到符合条件的就加入集合，避免重复尝试：

def greedy_solution(n=12, m=17):
    result = [0]
    candidate = 1
    max_32bit = 2**32 - 1
    
    while len(result) < n:
        valid = True
        for num in result:
            if hamming_distance(candidate, num) < m:
                valid = False
                break
        if valid:
            result.append(candidate)
            print(f"找到第{len(result)}个数字：{hex(candidate)}")
        candidate += 1
        if candidate > max_32bit:
            candidate = 1
    return result

# 调用生成结果
greedy_set = greedy_solution(12,17)

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