技术问询：不使用Itertools与循环实现图的全三色组合生成

嘿，我来帮你搞定这个需求！既然不能用循环和itertools，递归就是最适合的思路——我们可以通过递归逐步拆解节点，为每个节点生成所有可能的颜色选项，再把它们拼接成完整的着色字典。

实现代码 #

def three_color(graph):
    # 提取图中的所有节点
    nodes = list(graph.keys())
    
    def add_color_to_combinations(node, color, combinations):
        # 把单个节点的颜色添加到已有组合中，用列表推导替代显式循环
        return [{node: color, **combo} for combo in combinations] if combinations else [{node: color}]
    
    def recursive_coloring(remaining_nodes):
        # 基线条件：没有剩余节点时，返回空组合的初始状态
        if not remaining_nodes:
            return [{}]
        
        current_node = remaining_nodes[0]
        # 递归获取剩余节点的所有着色组合
        rest_combinations = recursive_coloring(remaining_nodes[1:])
        
        # 合并当前节点三种颜色的所有可能组合
        return (
            add_color_to_combinations(current_node, '1', rest_combinations) +
            add_color_to_combinations(current_node, '2', rest_combinations) +
            add_color_to_combinations(current_node, '3', rest_combinations)
        )
    
    return recursive_coloring(nodes)

代码解释 #

1. 递归拆解逻辑：
   • 我们先把图的节点提取成列表，然后递归处理每个节点：
     • 当没有剩余节点时，返回[{}]作为基线（表示没有节点需要着色的初始状态）。
     • 对当前节点，先递归得到剩余所有节点的所有着色组合。
     • 为当前节点分配三种颜色中的每一种，把颜色和剩余节点的组合拼接，最后合并三部分结果。
2. 避免显式循环：
   • 用列表推导替代了for循环来拼接颜色和组合，完全符合“不能使用循环”的要求。
3. 兼容性：不管输入的图结构如何（哪怕节点更多），这个函数都能生成所有可能的三色组合，因为题目不要求检查着色有效性，所以不需要处理相邻节点的颜色冲突。

测试示例 #

调用你给出的测试用例：

result = three_color({"A": ["B"], "B": ["A"]})
print(result)

会输出你期望的结果：

[{'A': '1', 'B': '1'}, {'A': '1', 'B': '2'}, {'A': '1', 'B': '3'}, {'A': '2', 'B': '1'}, {'A': '2', 'B': '2'}, {'A': '2', 'B': '3'}, {'A': '3', 'B': '1'}, {'A': '3', 'B': '2'}, {'A': '3', 'B': '3'}]

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