найти непрерывную последовательность в списке на основании последовательности в другом списке Python

Question

list1 = [1,5,6,7,8,9,0,9,8,7,6,5,4,3,2]
list2 = [9,8,7,6,5,4,3,2,1,0,3,5,2,5,7]

В списке list2 с начала массива идет последовательность (выделена жирным), точно такая же со сдвигом повторяется в списке list1 (выделена жирным). Мне достаточно 3-4 совпадений подряд, чтобы понять, что последовательность верная. Вернуть нужно правильные индексы из списка list1. Списки короткие для примера, в реальности они могут быть по 300-400 значений, сдвиг может быть на 100-200 индексов и значения могут быть пятизначными. Сами значения в списках в верной последовательности могут немного колебаться (примерно +3, -3), поэтому внутри сравнения надо еще проверять на эти колебания. Подскажите, есть ли решения на Python для этого?

Answer 1

def find_continuous_sequence(list1, list2, min_length=3, tolerance=3):
    def is_match(a, b):
        return abs(a - b) <= tolerance

    max_match_count = 0
    current_match_count = 0
    best_start = -1
    current_start = -1

    for i in range(len(list1)):
        for j in range(len(list2)):
            if is_match(list1[i], list2[j]):
                if current_match_count == 0:
                    current_start = i
                current_match_count += 1
                if current_match_count > max_match_count:
                    max_match_count = current_match_count
                    best_start = current_start
            else:
                current_match_count = 0

    if max_match_count >= min_length:
        return list1[best_start:best_start + max_match_count]
    else:
        return []

list1 = [1, 5, 6, 7, 8, 9, 0, 9, 8, 7, 6, 5, 4, 3, 2]
list2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 3, 5, 2, 5, 7]

result = find_continuous_sequence(list1, list2)
print(result)

Answer 2

Не уверен насколько правильно я Вас понял, но возможно такой вариант подходит под такую задачу:

def find(list1, list2, tolerance=3, min_sequence_length=3):
    result_sequence = []
    current_sequence = []

    for i in range(len(list1)):
        for j in range(len(list2)):
            k = 0
            current_sequence = []

            while (i + k < len(list1) and j + k < len(list2) and
                   abs(list1[i + k] - list2[j + k]) <= tolerance):
                current_sequence.append(list1[i + k])
                k += 1

            if len(current_sequence) > len(result_sequence):
                result_sequence = current_sequence

    if len(result_sequence) >= min_sequence_length:
        return result_sequence
    return None

list1 = [1, 5, 6, 7, 8, 9, 0, 9, 8, 7, 6, 5, 4, 3, 2]
list2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 3, 5, 2, 5, 7]

result = find(list1, list2)
if result:
    print("Последовательность в list1:", result)
else:
    print("Не найдено.")

>>> Последовательность в list1: [9, 8, 7, 6, 5, 4, 3, 2]

Если, к примеру, заменить 0 в первом списке на 12, то:

>>> Последовательность в list1: [12, 9, 8, 7, 6, 5, 4, 3, 2]

БЛОГ НА HUSL

найти непрерывную последовательность в списке на основании последовательности в другом списке Python

Ответы (2 шт):