我正在尝试解决 Python/Pandas 中的一个问题,我认为这与最长路径算法密切相关。我正在使用的 DataFrame 具有以下结构:
import numpy as np
import pandas as pd
data = {
"cusID": ["001", "001", "001", "001", "001", "001", "002", "002", "002"],
"start": ["A", "B", "C", "D", "A", "E", "B", "C", "D"],
"end": ["B", "C", "D", "A", "E", "A", "C", "D", "E"]
}
df = pd.DataFrame(data)
print(df)
cusID start end
0 001 A B
1 001 B C
2 001 C D
3 001 D A
4 001 A E
5 001 E A
6 002 B C
7 002 C D
8 002 D E
对于每个客户,我想找到不包含 A 的最长序列。例如,对于客户 001,可以查看序列如下:A -> B -> C -> D -> A -> E -> A
哪里 B -> C -> D 是长度为 3 的最长序列。
我正在寻找的结果数据帧如下:
cusID longestSeq
0 001 3
1 002 4
虽然我无法编写太多代码来解决这个问题,但这里有一些我的想法: 首先,很明显我需要按 cusID 对原始 DataFrame 进行分组,以分别分析两个序列中的每一个。我的一个想法是应用一些函数将 DataFrame 转换为这种格式: cusID seq
0 001 [A, B, C, D, A, E, A]
1 002 [B, C, D, E]
然后分别处理每个列表,并使用某种计数器来获取排除 A 的路径长度的最大值。我的问题是将该逻辑转录为代码(如果正确)。任何帮助,将不胜感激。
最佳答案
第一步是对序列进行归一化。
seqs = pd.concat([
df.drop(columns="end").rename(columns={"start":"node"}),
df.groupby("cusID").tail(1).drop(columns="start").rename(columns={"end":"node"})
])
seqs = seqs.sort_values("cusID", kind="mergesort").reset_index(drop=True)
>>> seqs
cusID node
0 001 A
1 001 B
2 001 C
3 001 D
4 001 A
5 001 E
6 001 A
7 002 B
8 002 C
9 002 D
10 002 E
然后,使用 zero_runs
我们定义:def longest_non_a(seq):
eqa = seq == "A"
runs = zero_runs(eqa)
return (runs[:,1] - runs[:,0]).max()
result = seqs.groupby("cusID")["node"].apply(longest_non_a)
>>> result
cusID
001 3
002 4
Name: node, dtype: int64
关于python - 有条件的最长路径查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64696711/