如何高效查找无重复数字/字母的数-字母对组合？

给定数-字母对列表：

all_edges_array = [
                   [1,'a'],[1,'b'],[1,'c'],
                   [2,'c'],[2,'d'],
                   [3,'b'],[3,'c']
                  ]

注意输入并非数字与字母的全交叉乘积（例如缺少[2, 'a']）。需要高效查找满足以下条件的数-字母对组合：

• 组合内任意两个数-字母对的数字或字母均不重复。

有效结果示例 #

对于上述输入，有效结果共5个：

[([1, 'a'], [2, 'c'], [3, 'b']), ([1, 'a'], [2, 'd'], [3, 'b']), ([1, 'a'], [2, 'd'], [3, 'c']), ([1, 'b'], [2, 'd'], [3, 'c']), ([1, 'c'], [2, 'd'], [3, 'b'])]

无效组合示例 #

• ([1, 'a'], [1, 'b'], [3, 'c'])：包含重复数字1
• ([1, 'b'], [2, 'c'], [3, 'b'])：包含重复字母b

当前实现（暴力法） #

使用itertools.combinations生成所有组合后过滤，代码如下：

from itertools import combinations

number_letter_dict = {1:['a','b','c'], 2:['c','d'], 3:['b','c']}

# 创建边列表
all_edges_array = []
for key in number_letter_dict.keys():
    for item in number_letter_dict[key]:
        all_edges_array.append([key, item])

# 需要选择的对数等于数字的数量
number_of_connections = len(number_letter_dict.keys())

# 生成所有可能的组合（共35个）
all_combinations_array = list(combinations(all_edges_array, number_of_connections))

# 过滤有效组合
all_good_combinations = []
for collection in all_combinations_array:
    duplicated_item = False
    seen_indices = []
    for item in collection:
        if item[0] in seen_indices:
            duplicated_item = True
            break
        if item[1] in seen_indices:
            duplicated_item = True
            break
        seen_indices.append(item[0])
        seen_indices.append(item[1])
    if not duplicated_item:
        all_good_combinations.append(collection)

该方法效率极低，随着数-字母对数量增加，无效组合占比急剧升高，处理实际输入时耗时过长。需要从避免生成无效组合入手优化算法。

核心思路是按数字分组，依次为每个数字选择未被使用过的字母，每一步都实时排除重复的字母，从根源上避免生成无效组合。

实现代码 #

def find_valid_combinations(number_letter_dict):
    # 固定数字遍历顺序，确保结果一致性
    numbers = list(number_letter_dict.keys())
    result = []
    
    def backtrack(index, used_letters, current_combination):
        # 终止条件：所有数字都已匹配到唯一字母
        if index == len(numbers):
            result.append(tuple(current_combination.copy()))
            return
        
        current_num = numbers[index]
        # 遍历当前数字的所有可选字母
        for letter in number_letter_dict[current_num]:
            # 仅选择未被使用过的字母
            if letter not in used_letters:
                used_letters.add(letter)
                current_combination.append([current_num, letter])
                # 递归处理下一个数字
                backtrack(index + 1, used_letters, current_combination)
                # 回溯：撤销当前选择，尝试下一个字母
                current_combination.pop()
                used_letters.remove(letter)
    
    backtrack(0, set(), [])
    return result

# 测试
number_letter_dict = {1:['a','b','c'], 2:['c','d'], 3:['b','c']}
print(find_valid_combinations(number_letter_dict))

优化原理 #

1. 天然避免重复数字：按数字分组依次选择，每个数字仅被处理一次，无需额外判断重复数字。
2. 实时剪枝：每一步只选择未被使用的字母，直接跳过会导致重复的选项，不会生成无效的中间组合。
3. 资源占用低：仅在有效分支上递归，不会生成大量无效组合占用内存和计算资源。

效率对比 #

对于示例输入，暴力法需要生成35个组合再过滤，而回溯法仅生成必要的中间分支，直接得到5个有效结果。当输入规模增大时，这种提前剪枝的优势会呈指数级放大。

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