Combining Two lists without Itertools

Question

For part of a project, I have to show all possible combinations of three-colorings for a given graph, defined in a dictionary. This does not check for valid colorings, as it is simply a helper method.

Example

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

However, we are prohibited from importing any libraries. Currently, I am working with this solution and trying to transfer it without using product()

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

My current solution is based on the fact, according to the documentation, product(A, B) returns the same as ((x,y) for x in A for y in B).

Currently, I have

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

This gives me the correct answer when using graph {"A":["B"], "B":["A"]}, but it doesn't seem to work when with any other number of vertices.

Example 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}]

Any guidance or assistance is greatly appreciated.

Answer 1

You can use simple recursion with a generator function, then use zip to pair the full colorings to the graph:

def full_product(d, d1, current = []):
   if d == len(current):
      yield current
   else:
      for i in range(d):
        for b in range(1, d1):
           yield from full_product(d, d1, current + [b])

def final_results(data):
  def wrapper():
    for colors in data():
       full_set = set(reduce(lambda x, y:x+y, [[a]+b for a, b in colors.items()]))
       result = list(full_product(len(full_set), 4))
       last_result = [a for i, a in enumerate(result) if all(a != c for c in result[:i])]
       yield [dict(zip(full_set, i)) for i in last_result]
  return wrapper

@final_results
def full_results():
   return [{"A":["B"], "B":["A"]}, {"A":["B","C"], "B":["A"], "C":["A"]}]

print(list(full_results()))

Output:

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

Answer 2

If you check out the itertools documentation, they provide implementations of most of their builtin functions.

For product, the only difference in the one they provide is that the itertools implementation does not build up intermediate results in memory.

You can take the function provided in the documentation, and use it as your product function in your example:

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"]}))

Output:

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