CODEWITHSUNDEEP
pythonlistiteration
AATU
AATU

Reputation: 87

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

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.

Upvotes: 0

Views: 307

Answers (4)

Alain T.
Alain T.

Reputation: 42143

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

Upvotes: 0

user17903384
user17903384

Reputation:

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]

Upvotes: 0

dawg
dawg

Reputation: 103874

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

Upvotes: 2

TitoOrt
TitoOrt

Reputation: 1305

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.

Upvotes: 0

Related Questions