确定哪些列表满足要求的算法

Question

我在想出一个算法时卡住了，现在我不知道该怎么做。

我需要从 a 到 d，但只能滚动浏览这些列表：

[e, d]
[a, b, c]
[d, a]
[a, b]
[a, e, b]

这当然是一个简单的例子，解决方案是：

[a → d]         // 3rd line
[a → e → d]     // 5th line + 1st line
[a → b → e → d] // 2nd + 5th + 1st line

但我必须在Python中解决它。我想出了两种方法来解决这个问题，第一种是使用 for 循环，但是循环开始重复并且非常耗时，所以我采用了第 2 个想法。我正在考虑创建一个以 a 开头并以 d 结尾的所有可能变体的列表。然后在我们指定的列表中检查这是否可行。

from itertools import permutations
 
lst = ['a', 'b', 'c', 'd', 'e']

x = 'a'
y = 'd'

for i in range(1, len(lst)):
    perm = permutations(lst, i+1)

    for j in list(perm):
        if (j[0] == x) and (j[-1] == y):
            print(j)

但不知何故我卡住了，我不知道现在该怎么办。有人可以给我提示吗？还是我做错了？

编辑：

我正在尝试找到所有路径并打印它们。

Answer 1

这是一个图问题，其中列表是节点之间的无向边。例如：

[a, b, c]

表示从a到b和c，从b到a和c存在无向边，并且从 c 到 a 和 b。当然，a--b，也就是b--a。为了清楚起见，我重复了上面的边缘。

因此，您要做的是创建一个表示所有这些边的邻接表并应用回溯，因为您需要从源到目标的所有可能路径。

下面是一些向您展示想法的代码：

adj_list = collections.defaultdict(set)
for row in rows:
  for i, el in enumerate(row):
    for j in range(i+1, len(row):
        adj_list[el].add(row[j])
        adj_list[row[j]].add(el)

def backtrack(node, adj_list, seen, partial_res, res):
  if node == target:
    res.append(partial_res[:])
  
  for neighbor in adj_list[node]:
    if neighbor in seen: continue
    seen.add(neighbor)
    partial_res.append(neighbor)
    backtrack(neighbor, adj_list, seen, partial_res, res)
    partial_res.pop()
    seen.remove(neighbor)

res = []
backtrack(start, adj_list, set(), [], res)
print(res)

我没有运行这个。但是代码应该给出回溯如何工作的概念。这是一个 dfs，您可以在其中检查每条可能的路径并跟踪您走过的边缘。如果它通向目的地，您将在最终结果中保存它的副本。

请注意，此算法在每条路径中只访问每个节点一次。

确定哪些列表满足要求的算法

Algorithm to determine which lists satisfy requirement

python

algorithm

combinations

编辑：