我有一个长度相同的任意数量的嵌套列表(为了简单起见,我们说两个),看起来是这样的。
EDIT在这次编辑中,我把例子列表改成了两个特定的,似乎会引起麻烦。
l1 = [[96, 110], [49, 95, 122], [173, 218], [30], [80, 159], [95, 119, 150, 168]]
l2 = [[25, 110], [63, 126], [130, 222], [42], [3], [94, 119, 150, 176]]
现在我想用一个函数来检查每一个索引是否存在条目(以及哪些条目和有多少条目) 在给定范围内的每一个列表中,并返回它们。 假设范围是20。在这个例子中,我想返回
[[[110, 96], [110, 110]], [[63, 49], [126, 122]], [222, 218], [42, 30], [], [[95,94],[119, 119], [150, 150], [176, 168]]]
我知道,对于 两种 列表,我可以使用 itertools
像这样。
result = []
for i in range(len(l1): # the lists have the same length
result.append(
[[a,b] for (a, b) in itertools.product(l1[i], l2[i])
if a-20 <= b <=a+20])
在这个例子中,我需要检查我在嵌套列表中的条目是否是int, 然后用另一种方法来比较我的条目,但这是次要的。最大的问题是如何用两个以上的列表来做。我曾想过一个递归的解决方案,但无法想出合适的办法。
EDIT 有两个以上的名单,我的意思是我有更多的名单,如 l1
或 l2
的长度和其他的一样。
@MishaMelnyk 和 @AlainT 给出的解决方案已经很有帮助了,但是结果取决于列表的顺序,给定的解决方案的顺序是 l1, l2:
[[[110, 96], [110, 110]], [[63, 49], [126, 122]], [[222, 218]], [[42, 30]], [], [[119, 119], [150, 150], [176, 168]]]
或顺序为l2, l1
[[[110, 110]], [], [], [[30, 42]], [], [[95, 94], [119, 119], [150, 150], [168, 150]]]
乐于接受任何建议
这是我根据你提到的内容做的。
l1 = [[80,112,270],[20,78], 6, [99,134,240,300]]
l2 = [30, [22,84],[7,122,189,279],[67,100]]
l3 = [60, [25, 70], [2], [110]]
def makeZip(maxRange, *args):
for l in args: #For each index in the lists, converts any integers to lists
for i in range(len(l)):
if type(l[i]) == int:
l[i] = [l[i]]
z = zip(*args)
#Zip makes lists for each video with all of the entries
#Basically Equivilant to transposing a matrix in Lin Alg
matches = []
for l in z: #For each video, generates matching pairs
videoMatches = []
for m in makeMatch(maxRange, l): #For all of the pairs, add to list
videoMatches.append(m)
matches.append(videoMatches) #Add the list to the main list
return matches
def makeMatch(maxRange, l):
if len(l) == 1: #If only one list (person) then return all of the values sequentially (generator)
for i in l[0]:
yield [i]
return
matches = []
for n in makeMatch(maxRange, l[1:]): #for each of the generated match from a recursive call
for i in l[0]: #For all of the values of the current person
if all([abs(i - x) < maxRange for x in n]): #Check if value works for all of the values already in the match
matches.append([i] + n) #Sucessful match
for m in matches: #when done with all of the matches, return them sequentially (generator)
yield m
for m in makeZip(20, l1, l2, l3):
print(m)
你可能需要重新命名这些变量。希望输出的是三个列表应该有的结果。
您可能会遇到的一个问题是,我很确定在最坏的情况下,所有的东西都匹配的O(numVideos^numPeople)。不过,关于复杂性可能是错的。
一旦你解决了两个列表的问题,你就可以反复使用,从前两个开始,然后合并列表1和列表2,并执行合并后的列表和列表3之间的检查,然后将列表3合并到该列表,并将合并后的列表与列表4一起处理,以此类推。
通过对list1中的子列表进行排序,并使用bisect_left找到第一个元素'b'是>=到a-20,然后在排序的元素中依次前进,直到超越a+20,可以大大加快两个列表之间的比较逻辑。 这将使你的时间复杂度达到O(NlogM),而不是O(N*M),当你在多列表过程中合并列表时,这将变得更加重要。
下面是一个多列表过程的具体例子。
请注意,我没有在matchSubLists函数中加入二分法搜索优化(只有在你的子列表足够大的情况下才需要这样做
def matchSubLists(sA,sB,match):
return [ (a,b) for b in sB for a in sA if match(a,b) ]
def match2Lists(A,B,match):
return [ matchSubLists(sA,sB,match) for sA,sB in zip(A,B)]
def merge2Lists(A,B):
return [ sA+sB for sA,sB in zip(A,B) ]
def matchMultiLists(*L,match):
result = [[] for _ in L[0]]
merged = L[0]
for Ln in L[1:]:
matches = match2Lists(merged,Ln,match)
result = merge2Lists(result,matches)
merged = merge2Lists(merged,Ln)
return result
ouput.我使用了一个条目子列表来代替int值,以实现更一致的数据结构,避免逻辑中不必要的异常。
l1 = [[80,112,270], [20,78], [6], [99,134,240,300]]
l2 = [[30], [22,84], [7,122,189,279], [67,100]]
l3 = [[60], [25, 70], [2], [110]]
result = matchMultiLists(l1,l2,l3, match=lambda a,b:abs(a-b)<=20)
print(result)
[
[(80, 60)],
[(20, 22), (78, 84), (20, 25), (22, 25), (78, 70), (84, 70)],
[(6, 7), (6, 2), (7, 2)],
[(99, 100), (99, 110), (100, 110)]
]
我使用了一个条目子列表而不是int值,以使数据结构更加一致,避免逻辑中不必要的异常。
[编辑]
如果你希望在调用matchMultiList时,输出的结果与列表的顺序无关,你可以在返回结果之前添加一个排序。
def matchMultiLists(*L,match):
result = [[] for _ in L[0]]
merged = L[0]
for Ln in L[1:]:
matches = match2Lists(merged,Ln,match)
result = merge2Lists(result,matches)
merged = merge2Lists(merged,Ln)
# consistently ordered result (2-level sort)
result = [ sorted( map(tuple,map(sorted,sR)) ) for sR in result ]
return result
因为你可以在两个列表中使用matchMultiLists, 你不需要在match2Lists()函数中添加排序。其实这3个单行函数可以定义在matchMultiLists()函数里面,避免暴露它们。
的输出。
l1=[[96, 110], [49, 95, 122], [173, 218], [30], [80, 159], [95, 119, 150, 168]]
l2=[[25, 110], [63, 126], [130, 222], [42], [3], [94, 119, 150, 176]]
range20 = lambda a,b:abs(a-b)<=20
print(matchMultiLists(l1,l2, match=range20))
[[(96, 110), (110, 110)], [(49, 63), (122, 126)], [(218, 222)], [(30, 42)], [], [(94, 95), (119, 119), (150, 150), (150, 168), (168, 176)]]
print(matchMultiLists(l2,l1, match=range20))
[[(96, 110), (110, 110)], [(49, 63), (122, 126)], [(218, 222)], [(30, 42)], [], [(94, 95), (119, 119), (150, 150), (150, 168), (168, 176)]]
你可以扩展你的解决方案,首先选择所有可能的子列表组合(在同一索引下),使用 combinations
,然后再使用以下方法查看所有的项目组合 product
. 类似于。
import itertools
result = []
for sub_lists in zip(l1, l2 ,l3):
for couple_subs in itertools.combinations(sub_lists, 2):
result.append(
[[a,b] for a, b in itertools.product(*couple_subs)
if abs(a-b) <= 20])
为了处理未知级别的嵌套,你可以先将子列表扁平化,然后再将它们传递给产品。
def flatten(l):
for el in l:
if isinstance(el, list):
yield from flatten(el)
else:
yield el
现在你可以在上面的代码中使用这个方法:
[[a,b] for a, b in itertools.product(flatten(couple_subs[0]), flatten(couple_subs[1]))
if abs(a-b) <= 20]
例:
import itertools
l1 = [[1, [4, 11], 2], [3,4]]
l2 = [[5,6], [7,8]]
l3 = [[9, 10], [11, 12]]
result = []
def flatten(l):
for el in l:
if isinstance(el, list):
yield from flatten(el)
else:
yield el
for sub_lists in zip(l1, l2 ,l3):
for couple_subs in itertools.combinations(sub_lists, 2):
result.append(
[[a,b] for a, b in itertools.product(flatten(couple_subs[0]), flatten(couple_subs[1]))
if abs(a-b) <= 3])
print(result)
Gives:
[[[4, 5], [4, 6], [2, 5]], [[11, 9], [11, 10]], [[6, 9]], [[4, 7]], [], [[8, 11]]]