python - Pandas 中的递归操作

Question

我有一个像这样的数据帧:

vals = {"operator": [1, 1, 1, 2, 3, 5], "nextval": [2, 3, 6, 4, 5, 6]}
df = pd.DataFrame(vals)

   operator  nextval
0         1        2
1         1        3
2         1        6
3         2        4
4         3        5
5         5        6

我想要做的是使用运算符和 nextval 获取从起点(如 1)到终点(如 6)的所有可能路径的列表，而不是严格意义上的最短路径。
输出可以很灵活，但我正在寻找这样的东西或传达这一点的东西:

1 -> 6
1 -> 2 -> 4 
1 -> 3 -> 5 -> 6

我能够关闭它，但不确定如何正确地进行递归，因为 dict 无法处理 2 个相同的键:

import pandas as pd

vals = {"operator": [1, 1, 1, 2, 3, 5], "nextval": [2, 3, 6, 4, 5, 6]}
df = pd.DataFrame(vals)

df1 = df.set_index("operator")

dictvals = {}
for x in df1.index.unique():
    dictvals[x] = []
    df2 = df1.loc[x]
    if isinstance(df2, pd.DataFrame):
        for idx, rowdata in df2.iterrows():
            dictvals[x].append(rowdata["nextval"])
    else:
        dictvals[x] = df2[0]

print(dictvals) 

{1: [2, 3, 6], 2: 4, 3: 5, 5: 6}

Answer 1

让我们尝试手动滚动解决方案，因为考虑这种递归算法是有教育意义的。 (当然，在现实世界中只使用现有的库是合适的；它可能会更加容错。)
您显示的代码构建了图形本身的可识别表示，但为了一致性，即使只有一个后继节点，也最好对值使用列表(或集合或元组)。我认为集合在这里最有意义，因为如果输入中有重复的条目，那么我们应该丢弃重复的图节点。所以让我们假设我们从以下开始:

graph = {1: {2, 3}, 2: {4}, 3: {5}, 5: {6}}

我们同意将自己限制在考虑有向无环图上。我建议可以递归地找到来自我们根节点的路径，如下所示:递归地检查来自每个后继节点的每条路径；累积这些结果，并在每个结果前面加上从根到相应后继的链接。
当然，当我们编写递归代码时，我们希望避免副作用，因为它们使推理变得更加困难。因此，让我们改为说:对于每个后继，对于来自该后继的每个 pat，所有路径的累积，定义为(从节点到后继的链接)+(从后继到结束的路径)。当然，我们表示“从节点到后继节点的链接”的方式只是当前节点名称和一个箭头；我们从递归中得到路径的其余部分，包括后继名称。
然后我们需要一个基本情况:如果没有后继者，那么我们有一条从这里到终点的路径(因为我们在终点)，这就是节点名称本身。如果我们的图中的死胡同用空集表示，我们的代码会更简单；但显然省略这些键更容易生成图形。所以我们将依靠 dict.get而不是在我们进行检查时索引。
嗯，第一部分对我来说听起来很像列表理解(有两个 for 子句`。对于基本情况，为了匹配它，我们需要一个包含一个路径的列表。这给了我们:

def paths(graph, root):
    successors = graph.get(root, set())
    if not successors:
        return [str(root)] # a single path starting here and going nowhere.
    return [
        f'{root} -> {path}'
        for successor in successors
        for path in paths(graph, successor)
    ]

让我们试试看:

>>> paths({1: {2, 3}, 2: {4}, 3: {5}, 5: {6}}, 1)
['1 -> 2 -> 4', '1 -> 3 -> 5 -> 6']

或者，您可以使用生成器表达式而不是列表推导式，甚至将其编写为递归生成器(使用 yield 和 yield from )。
(如果我们觉得足够厚脸皮，我们可以使用条件表达式继续函数式编程主题:)

def paths(graph, root):
    successors = graph.get(root, set())
    return [
        f'{root} -> {path}'
        for successor in successors
        for path in paths(graph, successor)
    ] if successors else [str(root)]