python - 在 Python 中返回所有可能的顶点着色组合

Question

我需要编写一个方法 three_color(graph) 将图形作为输入，并返回图形的所有可能的顶点着色，包括那些无效的顶点着色。我们使用字典表示图形，输出应该是字典列表。

three_color({“A” : [“B”], “B” : [“A”]}) should return 

{“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}

我在想出如何编写此方法的解决方案时遇到问题，因为我们不允许使用除复制之外的任何库来帮助我们。

我是 python 的新手，所以我不确定是否有一个我忽略的简单解决方案。非常感谢您提供帮助或指导。这就是我一直在尝试使用的:

def three_color(graph):
    vertices = []
    colorings = []
    color = {}
    for key in graph:
        vertices.append(key)
    for v in vertices:
        color[v] = 1
    colorings.append(copy.copy(color))

    for v in vertices:
        for v2 in vertices:
            for i in range(1,4):
                for j in range(1,4):
                    color[v] = i
                    color[v2] = j
                    colorings.append(copy.copy(color))

    #Get rid of duplicates
    new_c = []
    for c in colorings:
        if c not in new_c:
            new_c.append(c)

    return new_c

我知道这是完全错误的，但我无法正确考虑这些 for 循环。

Answer 1

因为这是一道作业题，所以我给出一个伪代码解法，你可以自己实现，希望能学到更多。

我偏爱递归，所以我将在这个解决方案中使用它。

take a graph as an argument:
    if the graph is empty, return the graph
    recursively color all the elements except the first, store the result as "tail"
    store the first element of the list as "head"
    for every element of tail, refered to as "element":
        add "head, color 1" + element to a final results list
        add "head, color 2" + element to a final results list
        add "head, color 3" + element to a final results list
    return final results