CODEWITHSUNDEEP
pythonarrays
Divisor_13
Divisor_13

Reputation: 61

How to find the longest consecutive chain of numbers in an array

For example we have [0, 1, 3, 5, 7, 8, 9, 10, 12, 13] .

The result must be 7, 8, 9, 10 because they are adjacent to each other, index wise and are consecutive integers, and also this chain is longer than 0, 1.

English is not my first language, excuse me if the writing is a bit obscure.

Upvotes: 4

Views: 3690

Answers (3)

pylang
pylang

Reputation: 44465

Code

Using itertools.groupby (similar to @Moses Koledoye's answer):

groups = [[y[1] for y in g] for k, g in itertools.groupby(enumerate(iterable), key=lambda x: x[0]-x[1])]
groups
# [[0, 1], [3], [5], [7, 8, 9, 10], [12, 13]]

max(groups, key=len)
# [7, 8, 9, 10]

Alternative

Consider the third-party tool more_itertools.consecutive_groups:

import more_itertools as mit


iterable = [0, 1, 3, 5, 7, 8, 9, 10, 12, 13]
max((list(g) for g in mit.consecutive_groups(iterable)), key=len)
# [7, 8, 9, 10]

Upvotes: 0

RomanPerekhrest
RomanPerekhrest

Reputation: 92854

Alternative solution using numpy module:

import numpy as np

nums = np.array([0, 1, 3, 5, 7, 8, 9, 10, 12, 13])
longest_seq = max(np.split(nums, np.where(np.diff(nums) != 1)[0]+1), key=len).tolist()    
print(longest_seq)

The output:

[7, 8, 9, 10]

  • np.where(np.diff(nums) != 1)[0]+1 - gets the indices of elements on which the array should be split (if difference between 2 consequtive numbers is not equal to 1, e.g. 3 and 5)

  • np.split(...) - split the array into sub-arrays

https://docs.scipy.org/doc/numpy-dev/reference/generated/numpy.diff.html#numpy.diff https://docs.scipy.org/doc/numpy-dev/reference/generated/numpy.split.html

Upvotes: 1

Moses Koledoye
Moses Koledoye

Reputation: 78546

Group the items into subsequences using itertools.groupby based on constant differences from an increasing count (provided by an itertools.count object), and then take the longest subsequence using the built-in max on key parameter len:

from itertools import groupby, count

lst = [0, 1, 3, 5, 7, 8, 9, 10, 12, 13]
c = count()
val = max((list(g) for _, g in groupby(lst, lambda x: x-next(c))), key=len)
print(val)
# [7, 8, 9, 10]

You may include the group key in the result (suppressed as _) to further understand how this works.

Upvotes: 5

Related Questions