Найти числа в пределах диапазона в произвольном количестве вложенных списков

Question

У меня есть произвольное количество вложенных списков (скажем, два для простоты) с одинаковой длиной, которые выглядят примерно так:

EDIT В этом редактировании я изменяю Примеры списков для двух c, которые, похоже, вызывают проблемы:

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 или нет, и использовать другой способ сравнения моих записей, но это скорее второстепенный.
большой вопрос, как это сделать с более чем двумя списками. У меня есть мысли о рекурсивном решении, но я не могу что-то решить должным образом. * той же длины, что и остальные.

Решения, предоставленные @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]]]

Рад любым предложениям

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 и т. д.

Сравнение logi c между двумя списками может быть значительно ускорено путем сортировки подсписок в list1 и использования bisect_left для поиска первого элемента 'b', который является > = до a-20, затем последовательно продвигайтесь по отсортированным элементам, пока не достигнете значения +20. Вы можете сделать это для каждого элемента «a» в соответствующем подсписке списка 2. Это даст вам временную сложность 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

output:

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, чтобы работать с более согласованной структурой данных и избежать ненужных исключений в логах c

[EDIT]

Если вы хотите, чтобы выходные данные были одинаковыми независимо от порядка списков в вызове 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 (), чтобы избежать их раскрытия.

output:

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

Answer 3

Вы можете расширить свое решение, чтобы сначала выбрать все возможные пары подсписок (с тем же индексом), используя combinations, а затем go через все пары элементов, используя 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]]]