python 在键具有多个值的图上运行DFS

krugob8w  于 2022-12-10  发布在  Python
关注(0)|答案(1)|浏览(127)

图像中的字典有整数键,并且有一个作为值的子列表列表。目标是找到每个键的所有子列表,使得上一个列表的第二个元素小于下一个列表的第二个元素。例如:[[3、4、7、5]、[4、5、2、7]、[6、7、5、4]、[9、10、7、3]]是可接受的输出。
其中3是第一个具有非空列表作为值的键,10是我们到达的最后一个键。我只需要找到通向10的所有可能路径。

nmpmafwu

nmpmafwu1#

您可以使用简单的列表操作:

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)

输出:

[[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]]

或者您可以使用generate all combinations from a list of lists

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))

其输出相同。

相关问题