-1
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.

MT0
  • 143,790
  • 11
  • 59
  • 117
endi__edi
  • 9
  • 4
  • The image could be easily be included as text in your question. – MrSmith42 Dec 09 '22 at 09:47
  • Where exactly did you get stuck? – MrSmith42 Dec 09 '22 at 09:48
  • Let's say i reach the list at key 3, so i pick the first one. For every element of it (in this case one) i need to go to : graph[element[1]], so i'd go to key 4 with value [4,5,2,7]. Now this list[1] == 5 but let's say it was 8. In that case i would need to go to key == 8 in dictionary but the value is a list of sublists so i would need a way to combine all the sublists in dict[8] . That's where i'm stuck since DFS works when i have one value per key. – endi__edi Dec 09 '22 at 09:53
  • 1
    Where is DFS, graph, ... in there? As described it is a simple list filtering problem. That can't be the problem. I guess you are using those tags (algorithm, dfs, graph aka graph-theory after edit) because you know it is an OR problem — either because you know things you haven't told, or because it is an OR assignment. What this dictionary represents? How can we "reach" 10. There are rules to your game, and we can't play if you don't enunciate them. – chrslg Dec 09 '22 at 10:50

1 Answers1

0

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.

MT0
  • 143,790
  • 11
  • 59
  • 117