在任意数量的嵌套列表中查找范围内的数字
Find numbers within a range in an arbitrary number of nested lists
我有任意数量的嵌套列表（为简单起见，假设两个），它们的长度相同，看起来像这样：
编辑
在此编辑中，我将示例列表更改为两个特定的，这似乎会引起麻烦：
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]]
现在我想要一个函数来检查每个索引是否存在位于给定范围内的每个列表中的条目（以及哪些条目和多少条目）并 returns 它们。
假设范围是 20。在这个例子中我想 return
[[[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 并使用另一种方法来比较我的条目，但这是次要的。
最大的问题是如何处理两个以上的列表。我想过递归解决方案，但无法正确解决问题。
编辑
对于两个以上的列表，我的意思是我有更多的列表，例如 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]]]
欢迎提出任何建议
一旦你解决了两个列表的问题，你可以从前两个开始迭代使用它，然后合并列表 1 和列表 2，并在合并的列表和列表 3 之间执行检查，然后合并列表 3到那个并用列表 4 处理合并列表，依此类推。
两个列表之间的比较逻辑可以通过对 list1 中的子列表进行排序并使用 bisect_left 找到第一个元素 'b' 即 >= 到 a-20，然后按顺序进行排序的元素，直到你超过 a+20。您可以对列表 2 的相应子列表中的每个项目 'a' 执行此操作。这将为您提供 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
输出：
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() 函数。实际上，可以在 matchMultiLists() 函数内部定义 3 个单行函数以避免暴露它们。
输出：
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)]]
这是我根据你说的做的：
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)。虽然复杂性可能是错误的。
您可以扩展您的解决方案，首先使用 combinations, and then go through all couples of items using 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)
给出：
[[[4, 5], [4, 6], [2, 5]], [[11, 9], [11, 10]], [[6, 9]], [[4, 7]], [], [[8, 11]]]
我有任意数量的嵌套列表（为简单起见，假设两个），它们的长度相同，看起来像这样：
编辑 在此编辑中，我将示例列表更改为两个特定的，这似乎会引起麻烦：
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]]
现在我想要一个函数来检查每个索引是否存在位于给定范围内的每个列表中的条目（以及哪些条目和多少条目）并 returns 它们。
假设范围是 20。在这个例子中我想 return
[[[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 并使用另一种方法来比较我的条目，但这是次要的。
最大的问题是如何处理两个以上的列表。我想过递归解决方案，但无法正确解决问题。
编辑
对于两个以上的列表，我的意思是我有更多的列表，例如 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]]]
欢迎提出任何建议
一旦你解决了两个列表的问题，你可以从前两个开始迭代使用它，然后合并列表 1 和列表 2，并在合并的列表和列表 3 之间执行检查，然后合并列表 3到那个并用列表 4 处理合并列表，依此类推。
两个列表之间的比较逻辑可以通过对 list1 中的子列表进行排序并使用 bisect_left 找到第一个元素 'b' 即 >= 到 a-20，然后按顺序进行排序的元素，直到你超过 a+20。您可以对列表 2 的相应子列表中的每个项目 'a' 执行此操作。这将为您提供 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
输出：
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() 函数。实际上，可以在 matchMultiLists() 函数内部定义 3 个单行函数以避免暴露它们。
输出：
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)]]
这是我根据你说的做的：
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)。虽然复杂性可能是错误的。
您可以扩展您的解决方案，首先使用 combinations, and then go through all couples of items using 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)
给出：
[[[4, 5], [4, 6], [2, 5]], [[11, 9], [11, 10]], [[6, 9]], [[4, 7]], [], [[8, 11]]]