python - 不使用 Itertools 组合两个列表

Question

对于项目的一部分，我必须显示字典中定义的给定图形的三种颜色的所有可能组合。这不会检查有效的颜色，因为它只是一个辅助方法。

示例

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

 Should give us:

 [{'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'}]

但是，我们被禁止导入任何库。目前，我正在使用此解决方案并尝试在不使用product()的情况下传输它

coloring = ([dict(zip(graph, p)) for p in product(colors,repeat = len(graph))])

我当前的解决方案基于这样的事实，根据文档，product(A, B) 返回与 ((x,y) for x in A for y in B)。

目前，我已经

def three_color(graph):
    colors = ['1','2','3']

    coloring = ([dict(zip(graph, p)) for p in ((x,y) for x in colors for y in (range(1,4)))])
    #coloring = ([dict(zip(graph, p)) for p in product(colors,repeat = len(graph))])

    return coloring

这在使用图形 {"A":["B"], "B":["A"]} 时给了我正确的答案，但它似乎不起作用具有任何其他数量的顶点。

示例 2

three_color({"A":["B","C"], "B":["A"], "C":["A"]})

Should give us:
[{'A': '1', 'B': '1', 'C': '1'},
 {'A': '1', 'B': '1', 'C': '2'},
 {'A': '1', 'B': '1', 'C': '3'},
 {'A': '1', 'B': '2', 'C': '1'},
 {'A': '1', 'B': '2', 'C': '2'},
 {'A': '1', 'B': '2', 'C': '3'},
 {'A': '1', 'B': '3', 'C': '1'},
 {'A': '1', 'B': '3', 'C': '2'},
 {'A': '1', 'B': '3', 'C': '3'},
 {'A': '2', 'B': '1', 'C': '1'},
 {'A': '2', 'B': '1', 'C': '2'},
 {'A': '2', 'B': '1', 'C': '3'},
 {'A': '2', 'B': '2', 'C': '1'},
 {'A': '2', 'B': '2', 'C': '2'},
 {'A': '2', 'B': '2', 'C': '3'},
 {'A': '2', 'B': '3', 'C': '1'},
 {'A': '2', 'B': '3', 'C': '2'},
 {'A': '2', 'B': '3', 'C': '3'},
 {'A': '3', 'B': '1', 'C': '1'},
 {'A': '3', 'B': '1', 'C': '2'},
 {'A': '3', 'B': '1', 'C': '3'},
 {'A': '3', 'B': '2', 'C': '1'},
 {'A': '3', 'B': '2', 'C': '2'},
 {'A': '3', 'B': '2', 'C': '3'},
 {'A': '3', 'B': '3', 'C': '1'},
 {'A': '3', 'B': '3', 'C': '2'},
 {'A': '3', 'B': '3', 'C': '3'}]

But it gives me:
[{'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}]

非常感谢任何指导或帮助。

Answer 1

如果您查看itertools documentation ，它们提供了大部分内置函数的实现。

对于product ，它们提供的唯一区别是 itertools 实现不会在内存中构建中间结果。

您可以采用文档中提供的函数，并将其用作示例中的产品函数:

def product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

def coloring(graph):
  colors = ['1','2','3']
  return [dict(zip(graph, p)) for p in product(colors,repeat = len(graph))]

print(coloring({"A":["B","C"], "B":["A"], "C":["A"]}))

输出:

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