如何用Python枚举法统计1-14整数满足约束的配对方式数

核心思路 #

要避免重复计数（比如(1,2)和(2,1)视为同一对，不同配对顺序但组合一致的拆分视为同一种），最高效的方式是按最小未配对数优先配对的回溯策略：每次从剩余数字中取出最小的数，只枚举能和它满足「大数≥2×小数」的配对对象，再递归处理剩下的数字。这种方式天然避免重复，因为所有拆分都是从最小数开始构建，不会生成重复的组合，无需额外用集合去重。

基础实现代码 #

def count_valid_pairs(numbers):
    if not numbers:
        return 1
    total = 0
    # 取当前剩余数字中的最小值
    smallest = numbers[0]
    # 遍历所有可配对的大数
    for i in range(1, len(numbers)):
        if numbers[i] >= 2 * smallest:
            # 生成剔除当前配对后的剩余数字列表
            remaining = numbers[1:i] + numbers[i+1:]
            total += count_valid_pairs(remaining)
    return total

# 初始化有序数字列表（1到14）
initial_numbers = list(range(1, 15))
result = count_valid_pairs(initial_numbers)
print(f"符合条件的拆分方式数：{result}")

效率优化（针对更大数据量） #

当数字范围扩大时，重复的剩余数字集合会频繁出现，此时可以用记忆化缓存来避免重复计算：

from functools import lru_cache

def count_valid_pairs(numbers):
    # 转换为不可变的frozenset，用于记忆化缓存的键
    return _count_valid(frozenset(numbers))

@lru_cache(maxsize=None)
def _count_valid(num_set):
    if not num_set:
        return 1
    total = 0
    smallest = min(num_set)
    # 遍历所有符合条件的配对数
    for num in num_set:
        if num > smallest and num >= 2 * smallest:
            remaining = num_set - {smallest, num}
            total += _count_valid(remaining)
    return total

initial_numbers = set(range(1, 15))
result = count_valid_pairs(initial_numbers)
print(f"符合条件的拆分方式数：{result}")

优化说明：

1. 记忆化缓存：用lru_cache装饰递归函数，将已计算过的剩余数字集合结果缓存，避免重复递归计算，数据量越大优化效果越明显。
2. 集合操作：用frozenset作为缓存键（因为列表不可哈希），集合的差集操作能快速生成剩余数字集合。

为什么不直接枚举所有排列？ #

14个数的全排列是14!（约870亿），这个量级的计算完全不现实。而按最小数优先的回溯法会提前剪枝掉所有不符合条件的路径，实际计算量远小于全排列。

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