CODEWITHSUNDEEP
pythonlisttreecombinations
eladc
eladc

Reputation: 120

Python: Creating combinations from a list of lists in a tree-like data structure

I have a list of n number of pairs, with digits in every pair are between 1 and 70.

aList = [[1, 5], [1, 12],...,[5, 45], [5, 47],...,[45, 49], [45, 65], ...]

every pair in this list act as the root of the tree, and combinations are built from it.

In this example [1, 5] is the root:

#                    [45, 65]
#             [5,45]/           [y, k]--...
#            /      \[45,49]   /
#           |                 |
# root: [1,5]--[5, x] -- [x, y]--[y,z]--...
#           |                 |
#            \      /[47,?]    \
#             [5,47]            [y, j]--...
#                   \[47,?]

I am trying to crate combinations from pairs only if n[1] == n+1[0].

for example:

[1,5,45,49,...]
[1,5,45,65,...]
[1,5,47,x,y,k,...]
[1,5,47,x,y,z,...]
[1,5,47,x,y,j,...]
[1,5,47,?,...]
[1,5,47,?,??]

I tried to use itertools.product but it yields every possible combination.

Thanks in advance.

Upvotes: 1

Views: 1220

Answers (2)

Nuclearman
Nuclearman

Reputation: 5304

It seems I skimmed over the "In this example [1, 5] is the root:" bit and thus overcomplicated my previous answer a fair bit. A standard directed graph and Breadth-first search modified for path finding will do the job.

def directed_graph_from_edges(edges):
    graph = {}
    for a,b in edges:
        graph.setdefault(a,set())
        graph[a].add(b)
    return graph

The path finding algorithm then just takes an edge as an input rather than a single vertex. However, it still uses the last vertex in the path (last_vertex = path[-1]) as the next node to expand. Once again, I'll leave the path finding algorithm as an exercise.

Upvotes: 1

eladc
eladc

Reputation: 120

Thank you Nuclearman, your answer helped me to come up with a solution.

It's pretty dirty and I'm sure there's a better pythonic way writing it, but it's good enough for me.

def treeSearch(i):
     if i in graph.keys():
         return graph[i]
     else:
         return [0]

edges = aList
graph = {}
for a,b in edges:
    if a not in graph.keys():
        graph[a] = []
        for c,d in edges:
           if a == c:
               graph[a].append(d)

for key in graph:
    for k in graph[key]:
        for j in treeSearch(k):
            for h in treeSearch(j):
                for g in treeSearch(h):
                    for f in treeSearch(g):
                        for v in treeSearch(f):
                            print [key,k,j,h,g,f,v]

Upvotes: 0

Related Questions