How to find a variable sublist in a list with conditions?-CodePudding

I am trying to figure out the following problem. I have a list with integers.

list = [1, 2, 3, 5, 6, 9, 10]

The goal is to find the longest sub-list within the list. The sub-list is defined by having the difference between two integers not being more than 1 (or -1). In this example, the longest sub-list respecting this condition is:

lista = [1, 2, 3, 5, 6, 9, 10]
difference = []

i = 0
for number in range(len(lista)-1):
    diff = lista[i]-lista[i 1]
    difference.append(diff)
    i  = 1
print(difference)

winner = 0
ehdokas = 0
for a in difference:
    
    if a == 1 or a == -1:
        ehdokas  = 1
    else:
        if ehdokas > winner:
            winner = ehdokas
            ehdokas = 0
if ehdokas > winner:
    winner = ehdokas
            
print(winner)

Now, the "print(winner)" will print "2" whereas I wish that it would print "3" since the first three integers are "adjacent" to each other (1-2 = -1 , 2-3 = -1)

Basically I am trying to iterate through the list and calculate the difference between the adjacent integers and the calculate the consecutive number of "1" and "-1" in the "difference" list. This code works sometimes, depending on the list fed through, sometimes it doesn't. Any improvement proposals would be highly appreciated.

CodePudding user response：

Given:

lista = [1, 2, 3, 5, 6, 9, 10]

You can construct a new list of tuples that have the index and difference in the tuple:

diffs=[(i,f"{lista[i]}-{lista[i 1]}={lista[i]-lista[i 1]}",lista[i]-lista[i 1]) 
       for i in range(len(lista)-1)]
>>> m
[(0, '1-2=-1', -1), (1, '2-3=-1', -1), (2, '3-5=-2', -2), (3, '5-6=-1', -1), (4, '6-9=-3', -3), (5, '9-10=-1', -1)]

Given a list like that, you can use groupby, max to find the longest length of the sub lists that satisfy that condition:

from itertools import groupby 

lista = [1, 2, 3, 5, 6, 9, 10]  

m=max((list(v) for k,v in groupby(
    ((i,lista[i]-lista[i 1]) for i in range(len(lista)-1)), 
        key=lambda t: t[1] in (-1,0,1)) if k),key=len)

>>> m
[(0, -1), (1, -1)]

CodePudding user response：

A nice and simple solution based on more_itertools:

#!pip install more_itertools

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

import more_itertools as mit
sublists = []
for group in mit.consecutive_groups(l):
    sublists.append(list(group))
    
max(sublists, key=len)

This outputs:

[1,2,3]

Which is the longest sublist of consecutive numbers.

CodePudding user response：

Here's a solution without the use of libraries:

l = [1, 2, 3, 4, 10, 11, 20, 19, 18, 17, 16, 30, 29, 28, 27, 40, 41]

r = []

if len(l) > 1:
    t = [l[0]]
    for i in range(0, len(l)-1):
        if abs(l[i]-l[i 1]) == 1:
            t.append(l[i 1])
            if len(t) > len(r):
                r = t.copy()
        else:
            t.clear()
            t.append(l[i 1])
    print(r)

Which will print:

[20, 19, 18, 17, 16]

CodePudding user response：

Since you're interested in only finding the length of the longest subsequence, here is one option that only uses a single for-loop. Simply iterate over the list, compare a value with its subsequent value and if the difference is 1 or -1 increase running counter by 1 and if there is a gap, increase max_len if the current running counter is greater than previously evaluated one.

def length_of_longest_subsequence(lst):
    max_len = current = 1
    end_of_lst = len(lst)-2
    for idx, (i,j) in enumerate(zip(lst, lst[1:] [0])):
        if i-j in (-1,1):
            current  = 1
        else:
            if current > max_len:
                max_len = current
            current = 1
    return max_len

Output:

CodePudding user response：

You can get differences between items and their predecessor with zip(). This will allow you to generate a list of break positions (the indexes of items that cannot be combined with their predecessor). Using zip on these breaking positions will allow you to get the start and end indexes of subsets of the list that form groups of consecutive "compatible" items. The difference between start and end is the size of the corresponding group.

L  = [1, 2, 3, 5, 6, 9, 10]

breaks = [i for i,(a,b) in enumerate(zip(L,L[1:]),1) if abs(a-b)>1 ]
winner = max( e-s for s,e in zip([0] breaks,breaks [len(L)]) )

print(winner) # 3

If you want to see how the items are grouped, you can use the start/end indexes to get the subsets:

[ L[s:e] for s,e in zip([0] breaks,breaks [len(L)]) ]

[[1, 2, 3], [5, 6], [9, 10]]