Найти самый длинный последовательный подмассив (не отсортированный) -Python

Question

v = [1,2,3,11,5,8,9,10,11,6,4] в приведенном выше списке 1,2,3 являются последовательными числами (1-й последовательный набор).8,9,10,11 являются последовательными числами (2-й набор, самый большой).Как я могу найти этот 2-й сет?Этот код ниже дает последовательные числа:

for i in range(len(v)-1):
    if v[i+1]==v[i]+1:
        if v[i-1]!=v[i]-1:
             print(v[i])
        print(v[i]+1)

Output:1,2,3,8,9,10,11

Я думал о том, чтобы использовать что-то вроде ниже и добавить выходные данные в новый список, а затем узнать максимальное значение списка. Я не могу думать ологика объединения этих двух идей.

for i in range(len(v)-1):
    for j in range(i+1,len(v)):
        if v[j]-v[i]  

Я смотрел на этот пример , но я думаю, что решение отличается от того, что я ищу.Заранее спасибо за ваше время и предложение.

Answer 1

Вы можете выполнять итерации по списку и продолжать добавлять элемент в потенциально самый длинный последовательный подсписок, а также начинать новый, если элемент не является последовательным по отношению к последнему элементу подсписка, и назначать подсписок какновый самый длинный подсписок, если он длиннее текущего самого длинного подсписка:

candidate = []
longest = []
for i in v:
    if candidate and candidate[-1] != i - 1:
        if len(candidate) > len(longest):
            longest = candidate
        candidate = []
    candidate.append(i)
if len(candidate) > len(longest):
    longest = candidate

longest становится:

[8, 9, 10, 11]

Answer 2

Вы можете использовать различия между элементами и их индексами для группировки элементов, используя функцию ‘groupby ()’:

from itertools import groupby

l = [1, 2, 3, 11, 5, 8, 9, 10, 11, 6, 4]

gb = groupby(enumerate(l), lambda x: x[0] - x[1])
max(([i for _, i in g] for _, g in gb), key=len)
# [8, 9, 10, 11]

Answer 3

Ты довольно близко. Сохраните текущий цикл в виде списка, обновите лучший список, когда это необходимо, и очищайте его каждый раз, когда вы прерываете цикл. Следует позаботиться о включении последней группировки, если она появляется в самом конце списка.

v = [1,2,3,11,5,8,9,10,11,6,4]
best = []
run = []

for i in range(1, len(v) + 1):
    run.append(v[i-1])

    if i == len(v) or v[i-1] + 1 != v[i]:
        if len(best) < len(run):
            best = run

        run = []

print(best)

Выход:

[8, 9, 10, 11]

Answer 4

Вы можете использовать панд:

import pandas as pd

v=[1,2,3,11,5,8,9,10,11,6,4]

s = pd.Series(v)

sgc = s.groupby(s.diff().ne(1).cumsum()).transform('count')

result = s[sgc == sgc.max()].tolist()

result

Выход:

[8, 9, 10, 11]

подробности:

Создайте серию панд, используйте diff, чтобы вычислить разницу от предыдущего значения. Затем используйте ne для создания логического ряда, в котором разница не равна 1, затем cumsum этого логического ряда для создания групп, в которых все последовательные значения сгруппированы вместе. Используйте groupby с transform для подсчета размера группы для каждой записи. Наконец, используйте логическое индексирование, чтобы выбрать только те части серии, где количество в группе равно максимальному количеству всех групп. Затем преобразовать в массив, используя tolist.

Answer 5

Вы можете использовать sliding window для уменьшения размера и проверить, все ли числа находятся в порядке возрастания:

from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result


def longestConsecutiveSeq(s):
  for seq in (window(s, i) for i in range(len(s)-1, 1, -1)):
    for subseq in seq:
      l = list(subseq)
      if all((y-x) == 1 for (x, y) in zip(l, l[1:])):
        return l

print(longestConsecutiveSeq([1,2,3,11,5,8,9,10,11,6,4]))

Результат: [8, 9, 10, 11]

Этот алгоритм остановится на первом столкновении самого большого размера .