在嵌套列表的任意数量的范围内查找数字

Question

我有很多嵌套列表（为简单起见，请说两个），它们的长度相同，看起来像这样：

l1 = [[80,112,270],[20,78], 6,             [99,134,240,300]]
l2 = [30,          [22,84],[7,122,189,279],[67,100]]

现在，我需要一个函数，该函数针对每个索引检查在给定范围内的每个列表中是否存在条目（以及条目和数量），并返回它们。可以说范围是20。在此示例中，我想返回[[],[[20, 22], [78, 84]],[6,7],[99,100]]

我知道对于two列表，我可以这样使用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，其长度与其他列表相同。

很高兴提出任何建议

Answer 1

这是我根据您提到的内容所做的：

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）在所有情况都匹配的最坏情况下。但是，关于复杂性可能是错误的。

Answer 2

一旦解决了两个列表的问题，您可以从前两个开始迭代地使用它，然后合并列表1和列表2，并在合并的列表和列表3之间进行检查，然后将列表3合并到该列表和使用列表4处理合并的列表，依此类推。

两个列表之间的比较逻辑可以通过对list1中的子列表进行排序并使用bisect_left查找> =到a-20的第一个元素'b'，然后在排序的元素中顺序进行直到您超出a +来大大加快。 20您可以对列表2的相应子列表中的每个项“ a”执行此操作。这将使您的时间复杂度为O（NlogM）而不是O（N * M），当您将列表中的列表合并时，这将变得更加重要多列表过程。

Answer 3

您可以扩展解决方案，以首先使用combinations选择所有可能的子列表对（在同一索引下），然后使用combinations遍历所有项对。类似于：

product

Ex：

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])