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

Question

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.

don't use `list` as variable name, that's python list constructor keyword — azro, Jan 11 '22 at 17:15
The difference can be 0 but that is not something that I want to count. I wish to find the adjacent integers where the difference is +1 or -1. — AATU, Jan 11 '22 at 17:22
What is the question? What is wrong with your solution? When you stepped thru the code was there any place that it seemed to go wrong? — wwii, Jan 11 '22 at 17:24
[Iterate a list as pair (current, next) in Python](https://stackoverflow.com/questions/5434891/iterate-a-list-as-pair-current-next-in-python) has some solutions that facilitate getting adjacent pairs from the list. — wwii, Jan 11 '22 at 17:28
Although your criteria for *grouping* sub-sequences is different, you could probably adapt an answer from [Find monotonic sequences in a list?](https://stackoverflow.com/questions/17000300/find-monotonic-sequences-in-a-list) — wwii, Jan 11 '22 at 17:38

dawg · Answer 1 · 2022-01-11T17:53:40.947

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

score 0 · Answer 2 · answered Jan 11 '22 at 17:49

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.

score 0 · Answer 3 · answered Jan 11 '22 at 18:13

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]

Alain T. · Answer 4 · 2022-01-11T19:00:13.217

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

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

4 Answers4