我有一個包含范圍信息的隨機長度列表：list = [ [[7, 12], [6, 12], [38, 44], [25, 30], [25, 29]], [[0, 5], [1, 5], [2, 5], [12, 16], [13, 16], [20, 23], [29, 33], [30, 33]], [[5, 7], [6, 8], [7, 9], [8, 10], [9, 11], [10, 12], [16, 18], [17, 19], [18, 20], [23, 25], [24, 26], [25, 27], [26, 28], [27, 29], [33, 35], [34, 36], [35, 37], [36, 38], [37, 39], [38, 40], [39, 41], [40, 42], [41, 43], [42, 44]]]例如，第一個元素[[7, 12], [6, 12], [38, 44], [25, 30]]包含 4 個范圍 7-12、6-12、38-44 和 25-30 等。我需要找到長度給定列表長度的所有可能的鏈（鏈是一個連續(xù)范圍的數(shù)組，其中第一個范圍的結(jié)束==下一個范圍的開始），因為我可以并且應該從每行中只取一個范圍行的確切順序。因此，對于此示例列表：鏈將是 [[6, 12], [12, 16], [16, 18]]、 [[7, 12], [12, 16], [16, 18]]和 [[25, 30], [30, 33], [33, 35]][[25, 29], [29, 33], [33, 35]]現(xiàn)在我堅持使用超過三個長度的列表，無法提出遞歸解決方案。
2 回答
守著星空守著你
TA貢獻1799條經(jīng)驗 獲得超8個贊
您可以使用itertools.product迭代所有可能的鏈（每個“行”中 1 個范圍的所有組合），
然后通過一個檢查特定鏈是否合法的簡單函數(shù)過濾它們。
嘗試這個：
from itertools import product
def check_chain(chain):
prev_end = chain[0][1]
for start, end in chain[1:]:
if start != prev_end:
return False
prev_end = end
return True
all_candidate_chains = product(*list)
result = [[*chain] for chain in all_candidate_chains if check_chain(chain)]
print(result)
輸出：
[[[7, 12], [12, 16], [16, 18]], [[6, 12], [12, 16], [16, 18]], [[25, 30], [30, 33], [33, 35]]]
編輯：
也可以使用zip并用 1-linerall替換：check_chain
from itertools import product
result = [[*chain] for chain in product(*list) if all(end1 == start2 for (_, end1), (start2, _) in zip(chain, chain[1:]))]
print(result)
慕絲7291255
TA貢獻1859條經(jīng)驗 獲得超6個贊
您可以在不查看所有排列的情況下執(zhí)行此操作。從最后一項開始并制作一個字典，其中鍵是字典中的第一個值。然后在列表中向后工作，并根據(jù)添加到數(shù)組中的元組的第二個值查找前一個鍵：
最后，您將有一個字典，鍵為第一個列表的元組中的第一個值。此時您可以將值展平。
在這里，我在中間列表中添加了一對[12,9]，因此我可以看到它與分支路徑一起使用：
from collections import defaultdict
from itertools import chain
l = [
[[7, 12], [6, 12], [38, 44], [25, 30]],
[[0, 5], [1, 5], [2, 5], [12, 16], [12, 9],[13, 16], [20, 23], [29, 33], [30, 33]],
[[5, 7], [6, 8], [7, 9], [8, 10], [9, 11], [10, 12], [16, 18], [17, 19], [18, 20], [23, 25], [24, 26], [25, 27], [26, 28], [27, 29], [33, 35], [34, 36], [35, 37], [36, 38], [37, 39], [38, 40], [39, 41], [40, 42], [41, 43], [42, 44]]
]
d = defaultdict(list)
for k, v in l[-1]:
d[k].append([[k,v]])
for sub in reversed(l[:-1]):
ds = defaultdict(list)
for k, v in sub:
if v in d:
ds[k].extend([[k,v], *v2] for v2 in d[v] )
d = ds
list(chain.from_iterable(d.values()))
輸出：
[[[7, 12], [12, 16], [16, 18]],
[[7, 12], [12, 9], [9, 11]],
[[6, 12], [12, 16], [16, 18]],
[[6, 12], [12, 9], [9, 11]],
[[25, 30], [30, 33], [33, 35]]]
添加回答
舉報
0/150
提交
取消