在Python中，从列表中嵌套结构的平面表示创建索引，按字母顺序排序

Question

我有列表，其中每个条目代表一个嵌套结构，其中/代表结构中的每个级别。

['a','a/b/a','a/b','a/b/d',....]

我想获取这样一个列表并返回一个索引列表，其中每个级别按字母顺序排序。

如果我们有以下列表

['a','a/b','a/b/a','a/c','a/c/a','b']

它代表嵌套结构

'a':                   #1

    'b':               #1.1
         'a': ...      #1.1.1
    'c':               #1.2
         'a': ...      #1.2.1
'b' : ...              #2

我正在尝试获取输出

 ['1','1.1','1.1.1', '1.2','1.2.1','2']

但我对如何解决这个问题有真正的问题，它可以递归解决吗？或者对于每个级别由 分隔的任何通用列表，有什么方法可以解决这个问题/？该列表原本不一定是排序的，并且每个级别可以是任何通用词。

Answer 1

由于目标是简单地根据路径相对于相同前缀的其他路径的各自位置将路径转换为索引，因此根本不需要构建树。相反，按字母顺序迭代路径，同时使用集合的字典来跟踪每个级别路径的前缀，并连接每个级别的集合长度以进行输出：

def indices(paths):
    output = {}
    names = {}
    for index, path in sorted(enumerate(paths), key=lambda t: t[1]):
        counts = []
        prefixes = tuple(path.split('/'))
        for level, name in enumerate(prefixes):
            prefix = prefixes[:level]
            names.setdefault(prefix, set()).add(name)
            counts.append(len(names[prefix]))
        output[index] = '.'.join(map(str, counts))
    return list(map(output.get, range(len(output))))

以便：

print(indices(['a', 'a/b', 'a/b/a', 'a/c', 'a/c/a', 'b']))
print(indices(['a', 'c', 'b', 'a/b']))
print(indices(['a/b/c/d', 'a/b/d', 'a/b/c']))
print(indices(['abc/d', 'bcc/d']))
print(indices(['apple/cat','apple/dog', 'banana/dog']))

输出：

['1', '1.1', '1.1.1', '1.2', '1.2.1', '2']
['1', '3', '2', '1.1']
['1.1.1.1', '1.1.2', '1.1.1']
['1.1', '2.1']
['1.1', '1.2', '2.1']

演示： https: //replit.com/@blhsing/StainedMassivePi