Running DFS on a graph whose keys have multiple values-CodePudding

1 []
2 []
3 [[3, 4, 7, 5], [3, 10, 6, 10]]
4 [[4, 5, 2, 7]]
5 []
6 [[6, 7, 5, 4]]
7 [[7, 8, 4, 2]]
8 [[8, 9, 10, 4], [8, 9, 1, 10]]
9 [[9, 10, 7, 3], [9, 10, 7, 9], [9, 10, 3, 7]]
10 []

The dictinary in the image has integer keys and there is a list of sublists as values. The goal is to find all sublists of every key such that the second element of the previous list is less than the second element of the next. For example: [[3, 4, 7, 5],[4, 5, 2, 7],[6, 7, 5, 4],[9, 10, 7, 3]] is an acceptable output.

with 3 being the first key that has non empty list as value and 10 being the final key we reach. I just need to find all possible paths that lead to 10.

CodePudding user response：

You can use simple list manipulation:

import itertools

values = [
  [],
  [],
  [[3, 4, 7, 5], [3, 10, 6, 10]],
  [[4, 5, 2, 7]],
  [],
  [[6, 7, 5, 4]],
  [[7, 8, 4, 2]],
  [[8, 9, 10, 4], [8, 9, 1, 10]],
  [[9, 10, 7, 3], [9, 10, 7, 9], [9, 10, 3, 7]],
  []
]

# Remove the empty items from the list.
filter_empty     = [items for items in values if items]

# Append None to each sub-list after the first to allow for later items to not be picked.
values_with_none = [items   ([None] if index > 0 else []) for index, items in enumerate(filter_empty)]

# Generate all combinations of picking one item from each sub-list.
all_combinations = list(itertools.product(*values_with_none))

# Remove all the None elements from the sub-lists.
filter_nones     = [[v for v in arr if v is not None] for arr in all_combinations]

# Filter out all the sub-lists where the last element does not have a second element of 10.
ending_with_10   = [arr for arr in filter_nones if arr[-1][1] == 10]

# Filter out all the sub-lists where the second elements are not in order.
filter_lt        = [arr for arr in ending_with_10 if all(map(lambda v: v[0][1] < v[1][1], zip(arr[0:-1], arr[1:])))]

for arr in filter_lt:
    print(arr)

Which outputs:

[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [6, 7, 5, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [7, 8, 4, 2], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [4, 5, 2, 7], [9, 10, 7, 3]]
[[3, 4, 7, 5], [4, 5, 2, 7], [9, 10, 7, 9]]
[[3, 4, 7, 5], [4, 5, 2, 7], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [7, 8, 4, 2], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [6, 7, 5, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [6, 7, 5, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [6, 7, 5, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [7, 8, 4, 2], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [7, 8, 4, 2], [9, 10, 7, 3]]
[[3, 4, 7, 5], [7, 8, 4, 2], [9, 10, 7, 9]]
[[3, 4, 7, 5], [7, 8, 4, 2], [9, 10, 3, 7]]
[[3, 4, 7, 5], [8, 9, 10, 4], [9, 10, 7, 3]]
[[3, 4, 7, 5], [8, 9, 10, 4], [9, 10, 7, 9]]
[[3, 4, 7, 5], [8, 9, 10, 4], [9, 10, 3, 7]]
[[3, 4, 7, 5], [8, 9, 1, 10], [9, 10, 7, 3]]
[[3, 4, 7, 5], [8, 9, 1, 10], [9, 10, 7, 9]]
[[3, 4, 7, 5], [8, 9, 1, 10], [9, 10, 3, 7]]
[[3, 4, 7, 5], [9, 10, 7, 3]]
[[3, 4, 7, 5], [9, 10, 7, 9]]
[[3, 4, 7, 5], [9, 10, 3, 7]]
[[3, 10, 6, 10]]

Or you can generate all combinations from a list of lists using:

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

# Generate all combinations of picking one item from each sub-list.
all_combinations = list(product(*values_with_none))

Which outputs the same.