Introduction

This kind of problem usually has two layers: a list of candidate sets, and a graph that says which choices can follow which other choices. The plain Cartesian product gives every possible list formed by choosing one element from each set, while the graph acts as a filter that removes combinations whose adjacent choices are not connected.

From List of Sets to Set of Lists

Suppose you start with a list of sets:

1choices = [
2    {"A", "B"},
3    {"1", "2"},
4    {"x", "y"}
5]

The Cartesian product of these three sets is the set of all length-three lists where:

• the first item comes from the first set
• the second item comes from the second set
• the third item comes from the third set

In Python, that is:

1from itertools import product
2
3choices = [
4    {"A", "B"},
5    {"1", "2"},
6    {"x", "y"}
7]
8
9all_lists = [list(items) for items in product(*choices)]
10print(all_lists)

This turns a list of sets into a set of lists, or more precisely a collection of tuples or lists representing each valid selection combination.

Where the Graph Enters

Now imagine those symbols are vertices, and edges describe allowed transitions. For example:

1graph = {
2    "A": {"1"},
3    "B": {"1", "2"},
4    "1": {"x"},
5    "2": {"y"}
6}

Now not every Cartesian-product combination is acceptable. A list such as ["A", "2", "x"] is invalid because there is no edge from A to 2.

So the graph changes the problem from:

• generate every combination

to:

• generate only combinations that form a valid path

Filter the Cartesian Product

The simplest implementation is:

1. build the full Cartesian product
2. keep only the lists whose adjacent elements are connected in the graph

1from itertools import product
2
3choices = [
4    {"A", "B"},
5    {"1", "2"},
6    {"x", "y"}
7]
8
9graph = {
10    "A": {"1"},
11    "B": {"1", "2"},
12    "1": {"x"},
13    "2": {"y"}
14}
15
16def is_valid_path(path, graph):
17    return all(path[i + 1] in graph.get(path[i], set()) for i in range(len(path) - 1))
18
19valid_lists = [
20    list(path)
21    for path in product(*choices)
22    if is_valid_path(path, graph)
23]
24
25print(valid_lists)

This approach is easy to understand and good for small search spaces.

Use DFS When the Product Is Large

If each set is large, generating the full Cartesian product wastes work because most combinations may be invalid. A better approach is depth-first search that checks graph constraints as soon as each next choice is made.

1def generate_valid_lists(choices, graph):
2    result = []
3
4    def dfs(index, current):
5        if index == len(choices):
6            result.append(current.copy())
7            return
8
9        for candidate in choices[index]:
10            if not current or candidate in graph.get(current[-1], set()):
11                current.append(candidate)
12                dfs(index + 1, current)
13                current.pop()
14
15    dfs(0, [])
16    return result
17
18choices = [
19    {"A", "B"},
20    {"1", "2"},
21    {"x", "y"}
22]
23
24graph = {
25    "A": {"1"},
26    "B": {"1", "2"},
27    "1": {"x"},
28    "2": {"y"}
29}
30
31print(generate_valid_lists(choices, graph))

This is still conceptually the Cartesian-product problem, but the search is pruned by the graph before invalid combinations fully form.

Graph Interpretation Matters

The graph can mean different things depending on the problem domain:

• allowed transitions in a workflow
• legal states in a parser
• adjacency in a layered graph
• compatible symbols in a combinatorial search

The key abstraction stays the same. Each position has a candidate set, and the graph defines compatibility between consecutive selections.

If compatibility depends on more than one previous step, then a simple graph may not be enough. You may need a higher-order state representation where the node encodes additional history.

Complexity Tradeoff

If the set sizes are n1, n2, ..., nk, the full Cartesian product has size n1 * n2 * ... * nk. That grows very fast. Filtering afterward can be acceptable for tiny instances, but for real search problems it is usually better to prune early.

That is why DFS or dynamic programming often wins over "generate everything, then filter" once the graph constraints are meaningful.

Common Pitfalls

• Treating the plain Cartesian product as the final answer when the graph actually imposes compatibility constraints between adjacent choices.
• Generating the full product for a large search space even though graph checks could prune invalid branches early.
• Forgetting that a list of sets produces ordered selections, while a set by itself is unordered. Position still matters in the resulting lists.
• Using a graph that only models pairwise compatibility when the real constraint depends on longer history.
• Mixing mathematical terminology and data-structure terminology so loosely that it becomes unclear whether the output should be tuples, lists, paths, or sets.

Summary

• A list of sets naturally defines a Cartesian-product problem.
• The Cartesian product gives all possible ordered selections, one item per set.
• A graph can be used to filter or generate only the selections that form valid transitions.
• For small inputs, filtering the full product is simple and clear.
• For larger inputs, DFS with early pruning is the more practical way to produce the valid set of lists.