我有串列，其中每個條目代表一個嵌套結構，其中/代表結構中的每個級別。
['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']
但是我在如何解決這個問題上有真正的問題，它會被遞回解決嗎？或者對于每個級別由 分隔的任何通用串列，有什么方法可以解決這個問題/？串列原本不一定是排序的，每一層都可以是任何通用詞。
uj5u.com熱心網友回復：
這是我嘗試過的：
from operator import itemgetter
from functools import reduce
lst = ['a','a/b','a/b/a','a/c','a/c/a','b']
# build a dict
dct = {}
for keys in lst:
reduce(lambda d, k: d.setdefault(k, {}), keys.split('/'), dct)
print(dct) # {'a': {'b': {'a': {}}, 'c': {'a': {}}}, 'b': {}}
def read_dct(dct, prefix=None):
if not dct: # empty dict, i.e., at a leaf
return
sorted_items = sorted(dct.items(), key=itemgetter(0)) # sort on keys
for i, (_, v) in enumerate(sorted_items, start=1):
yield (current := f"{prefix}.{i}" if prefix else str(i))
yield from read_dct(v, current)
print([*read_dct(dct)]) # ['1', '1.1', '1.1.1', '1.2', '1.2.1', '2']
基本上，第一部分構建一個字典來表示樹結構。然后我使用遞回函式從字典中創建一個串列。
uj5u.com熱心網友回復：
這是與已接受答案類似的解決方案，但我認為它可能比該答案更正確。如果我正確理解了這個問題，那么對于輸入串列中的每個值，輸出串列中應該只有一個值。的輸入['a/b/c/d']應該導致['1.1.1.1']，而不是具有四個值的串列。
無論如何，這是我的解決方案，還有幾個額外的測驗用例：
def doit(inp):
def recursive_print(struct, sum=""):
if sum and struct[1]:
print(sum)
for i, key in enumerate(sorted(struct[0].keys())):
recursive_print(struct[0][key], sum ("." if sum else "") str(i 1))
struct = [{}, False]
for v in inp:
p = last = struct
for part in v.split('/'):
if part not in p[0]:
p[0][part] = [{}, False]
p = p[0][part]
p[1] = True
recursive_print(struct)
inp = ['a','a/b','a/b/a','a/c','a/c/a','b']
doit(inp)
print()
inp = ['a/b/c/d']
doit(inp)
print()
inp = ['joe','joe/sam','larry/curly/moe','jerry/jill','jerry/jill/tom','jerry/jill/tony','alice/jill/betty/davis/eyes','john']
doit(inp)
結果：
1
1.1
1.1.1
1.2
1.2.1
2
1.1.1.1
1.1.1.1.1
2.1
2.1.1
2.1.2
3
3.1
4
5.1.1
uj5u.com熱心網友回復：
由于目標是根據路徑相對于具有相同前綴的其他路徑各自的位置簡單地將路徑轉換為索引，因此根本不需要構建樹。相反，按字母順序遍歷路徑，同時使用集合的字典來跟蹤每個路徑級別的前綴，并連接每個級別的集合長度以進行輸出：
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
uj5u.com熱心網友回復：
由于被分隔的字串部分/可能具有不同的長度，因此您不能直接對字串進行排序。但是，通過在 上拆分字串/，您可以獲得元組，您可以按照您想要的方式直接對其進行排序：
strings = ['a','a/b/a','a/b','a/b/d', 'b/a', 'b']
keys = sorted(map(lambda s: s.split('/'), strings))
print(keys)
輸出：
[['a'], ['a', 'b'], ['a', 'b', 'a'], ['a', 'b', 'd'], ['b'], ['b', 'a']]
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/522072.html
標籤：Python算法