例如：
l1 = [1, 2, 3, 4]
l2 = [{2, 1}, {1, 3}]
l2 可以從概念上擴展為：
l2 = [[2, 1], [2, 3], [1, 1], [1, 3]]
或者
l2 = [[2, 3], [2, 1], [1, 3], [1, 1]]
這意味著只要l2匹配中的 4 個串列之一l1，它就是一個成功的匹配。由于[1, 3]匹配l1 = [1, 2, 3, 4]，整個l2可以匹配。
匹配的定義：
For each element e in lx, e must be in l1 too; and for any two sequential elements e1 and e2, if e1 appears before e2, then e1 must also appear before e2 in l1.
因此，一種解決方案可能是先將其展平l2為新的l2，然后all(e in iter_of_l1 for e in sublist_l2)可以使用。
來自l2的序列形成為：從l2中的集合中取出每個元素并將其放入串列中，這樣您就可以獲得多個串列。[1,3] 匹配 [1,2,3,4] 因為它是 l1 的子序列。
如何在不顯式擴展l2到串列串列的情況下進行匹配？
uj5u.com熱心網友回復：
解決方案
而不是檢查的平等的中l1和l2元素，檢查會員的的l1中的元素l2的元素。
一些可能的實作（在線嘗試！）：
it1 = iter(l1)
result = all(any(x in pool for x in it1)
for pool in l2)
it1 = iter(l1)
result = all(not pool.isdisjoint(it1)
for pool in l2)
it1 = iter(l1)
result = not any(pool.isdisjoint(it1)
for pool in l2)
from itertools import repeat
result = not any(map(set.isdisjoint, l2, repeat(iter(l1))))
基準
測驗
l1 = [0, 1, 2, 3, ..., 39]
l2 = [{0, 1}, {2, 3}, ..., {40, 41}]
次數：
5254.183 ms subseq_product
0.020 ms subseq_all_any
0.006 ms subseq_all_not_disjoint
0.005 ms subseq_not_any_disjoint
0.005 ms subseq_map_disjoint
1279.553 ms subseq_Alain
0.018 ms subseq_Alain_faster
請注意，subseq_product2 21 個 普通子序列會檢查并subseq_Alain嘗試 2 20 (?) 條遞回路徑。
嘗試使用更長輸入的快速解決方案：
l1 = list(range(1000))
l2 = [{i, i 1} for i in range(0, 1002, 2)]
次數：
0.285 ms subseq_all_any
0.058 ms subseq_all_not_disjoint
0.057 ms subseq_not_any_disjoint
0.031 ms subseq_map_disjoint
1.488 ms subseq_Alain_faster
完整的基準代碼（在線試用！）：
from timeit import timeit
from itertools import product, repeat
def subseq_product(l1, l2):
def is_subseq(x, y):
# Ordinary subsequence test,
# see https://stackoverflow.com/a/24017747
it = iter(y)
return all(c in it for c in x)
return any(is_subseq(p2, l1)
for p2 in product(*l2))
def subseq_all_any(l1, l2):
it1 = iter(l1)
return all(any(x in pool for x in it1)
for pool in l2)
def subseq_all_not_disjoint(l1, l2):
it1 = iter(l1)
return all(not pool.isdisjoint(it1)
for pool in l2)
def subseq_not_any_disjoint(l1, l2):
it1 = iter(l1)
return not any(pool.isdisjoint(it1)
for pool in l2)
def subseq_map_disjoint(l1, l2):
return not any(map(set.isdisjoint, l2, repeat(iter(l1))))
def subseq_Alain(A, S):
if not S: return True # all sets matched
for i,n in enumerate(A): # check for membership in 1st set
if n in S[0] and subseq_Alain(A[i 1:],S[1:]): # and matching rest
return True # found full match
return False
def subseq_Alain_faster(A, S):
if not S: return True # all sets matched
for i,n in enumerate(A): # check for membership in 1st set
if n in S[0]:
return subseq_Alain_faster(A[i 1:],S[1:]) # and matching rest
return False
def benchmark(funcs, args, number):
for _ in range(3):
for func in funcs:
t = timeit(lambda: func(*args), number=number) / number
print('%8.3f ms ' % (t * 1e3), func.__name__)
print()
l1 = list(range(40))
l2 = [{i, i 1} for i in range(0, 42, 2)]
funcs = [
subseq_product,
subseq_all_any,
subseq_all_not_disjoint,
subseq_not_any_disjoint,
subseq_map_disjoint,
subseq_Alain,
subseq_Alain_faster,
]
benchmark(funcs, (l1, l2), 1)
l1 = list(range(1000))
l2 = [{i, i 1} for i in range(0, 1002, 2)]
funcs = [
subseq_all_any,
subseq_all_not_disjoint,
subseq_not_any_disjoint,
subseq_map_disjoint,
subseq_Alain_faster,
]
benchmark(funcs, (l1, l2), 500)
uj5u.com熱心網友回復：
如果您的集合串列可以有兩個以上的專案，那么遞回函式可能是最好的：
def subMatch(A,S):
if not S: return True # all sets matched
for i,n in enumerate(A): # check for membership in 1st set
if n in S[0] and subMatch(A[i 1:],S[1:]): # and matching rest
return True # found full match
return False
輸出：
l1 = [1, 2, 3, 4]
l2 = [{2, 1}, {1, 3}]
print(subMatch(l1,l2)) # True
l1 = [1, 2, 3, 4]
l2 = [{2, 1}, {1, 3}, {3, 4}]
print(subMatch(l1,l2)) # True
l1 = [1, 2, 4, 3]
l2 = [{2, 1}, {1, 3}, {3, 4}]
print(subMatch(l1,l2)) # False
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/391232.html
標籤：Python