在列表中搜索顺序值的函数

Question

我有以下这个列表：

list = [
   [2, 'A', '1'],
   [6, 'A', '2'],
   [6, 'S', '3'],
   [9, 'A', '4'],
   [6, 'A', '5'],
   [6, 'A', '6'],
   [6, 'S', '7'],
   [9, 'A', '8'],
   [9, 'A', '9'],
   [6, 'A', '10'],
   [10, 'S', '11'],
   [13, 'S', '12'],
   [13, 'S', '13'],
   [16, 'A', '14']
]

列表的第一个位置是级别，第二个是节点的类型，第三个是值。

我需要把所有比前一个（i-1）级别高的值连接起来。每个级别可以有多个A和S类型，但每次我找到一个S类型时，我还需要继续查找，直到找到一个更高级别的S或A类型。我的期望输出是：

['1.2', '1.3.4', '1.5', '1.6', '1.7.8', '1.7.9', '1.10.11.13.14']

我尝试用以下代码来实现这个输出：

def concat_levels(levels):
     result = []
     stack = []
    
     for level in levels:
        num, typ, name = level
        
        while stack and stack [-1][0] >= num:
           stack.pop()
 
        if typ == 'A':
           stack.append((num,name))
        elif typ == 'S':
           if stack:
              current_path = '.'.join([x[1] for x in stack])
              result.append(current_path + '.' + name)
     return result

但是，当我运行我的函数时，得到了以下输出：

['1.3', '1.7', '1.10.11', '1.10.12', '1.10.13']

显然，我的函数只在type == 'S'时进行追加，但这是为什么呢？

背景：这个列表是一个抽象的pyspark数据框架模式，其中A代表数组类型，S代表结构类型。为什么12没有在输出中？因为12是一个结构（S类型）。输出是1.10.11.13.14，因为级别16表示值14在级别13的结构内部。由于模式是有序的，每当同一级别有两个S类型时，如果在S类型后出现A类型，那么最后一个S类型应该被考虑（始终遵循级别规则）。

Answer 1

如果我理解得没错，你想使用pandas，那么你想要把一系列的last值（在某个特定层级上看到的）通过一个expanding窗口连接起来，前提是这个层级is_monotonic_increasing并且不以"S"结尾：

import pandas as pd

df = pd.DataFrame(list_, columns=["level", "type", "value"])

DIFF = df["level"].diff(); HEAD = df.at[0, "value"]

def seq(wd):
    diff = DIFF.loc[wd.index]
    not_dup = wd["level"].ne(wd["level"].shift())
    is_mi = wd.loc[not_dup, "level"].is_monotonic_increasing
    return (
        wd.loc[(diff.le(0) if is_mi else diff.lt(0))[::-1].idxmax() :]
        .groupby("level")["value"].last()
    )

sequences = [
    ".".join([HEAD, *wd.pipe(seq)])
    for wd in list(df.expanding())[1:]
    if (wd["type"].iat[-1] != "S") and not (
        DIFF.lt(0).iat[wd.index[-1]]
        and DIFF.shift(-1).gt(0).iat[wd.index[-1]]
    )
]

输出：

print(sequences)

# ['1.2', '1.3.4', '1.5', '1.6', '1.7.8', '1.7.9', '1.10.11.13.14']

窗口：

 level type value   w1     w2     w3     w4     w5     w6     w7  
     2    A     1    1      1      1      1      1      1      1  
     6    A     2    2      -      -      -      -      -      -  
     6    S     3    -      3      -      -      -      -      -  
     9    A     4    -      4      -      -      -      -      -  
     6    A     5    -      -      5      -      -      -      -  
     6    A     6    -      -      -      6      -      -      -  
     6    S     7    -      -      -      -      7      7      -  
     9    A     8    -      -      -      -      8      -      -  
     9    A     9    -      -      -      -      -      9      -  
     6    A    10    -      -      -      -      -      -     10  
    10    S    11    -      -      -      -      -      -     11  
    13    S    12    -      -      -      -      -      -     -  
    13    S    13    -      -      -      -      -      -     13  
    16    A    14    -      -      -      -      -      -     14