Splitting a list on non-sequential numbers-CodePudding

I have an ordered list of entities, numbered in a broken sequence:

[1, 2, 3, 6, 7, 11, 17, 18, 19]

I'd like to break the list where there's a gap, and collect the results in a new list:

[[1, 2, 3], [6, 7], [11], [17, 18, 19]]

I have the feeling there's a name for what I want to do and probably a nice library function for it - but I can't think of it. Can anyone shine some light before I possibly reinvent a wheel?

edit: Thanks, folks, but I was asking if there's a name for this operation and an existing algorithm, not for implementations - this is what I came up with:

def group_adjoining(elements, key=lambda x: x):
    """Returns list of lists of contiguous elements

    :key: function to get key integer from list element
    """
    if not elements:
        return elements

    result = [[elements[0]]]

    for a, b in zip(elements, elements[1:]):
        if key(a)   1 == key(b):
            result[-1].append(b)
        else:
            result.append([b])

    return result

CodePudding user response：

I first came across more_itertools today, and I think this package is useful for this problem.

pip install more-itertools

from more_itertools import split_when

l = [1, 2, 3, 6, 7, 11, 17, 18, 19]
res = list(split_when(l, lambda a, b: a   1 != b))
print(res)

CodePudding user response：

Try greedy approach:

lst = [1, 2, 3, 6, 7, 11, 17, 18, 19]
res = []
tmp = []
prv = lst[0]
for l in lst:
    if l-prv > 1:
        res.append(tmp)
        tmp = []
    tmp.append(l)
    prv = l
res.append(tmp)
print(res)

Output: [[1, 2, 3], [6, 7], [11], [17, 18, 19]]

CodePudding user response：

You could use a simple generator.

def split(lst):
    result = []
    for item in lst:
        if (not result) or result[-1]   1 == item:
            result.append(item)
        else:
            yield result
            result = [item]
    if result:
        yield result


foo = [1, 2, 3, 6, 7, 11, 17, 18, 19]
result = [i for i in split(foo)]
print(result) # [[1, 2, 3], [6, 7], [11], [17, 18, 19]]

This assumes a sorted homogeneous list of int.

You could always avoid the sorted assumption with for item in sorted(lst):.

CodePudding user response：

It's pretty easy by using this simple function:

li = [1, 2, 3, 6, 7, 9, 10, 11, 12, 14, 16, 17, 18]

def split(li):
    result = []
    temp = [li[0]]
    for i in range(1, len(li)):
        if li[i] - temp[-1] == 1:
            temp.append(li[i])
        else:
            result.append(temp)
            temp = [li[i]]
    result.append(temp)
    return result

print(split(li))

Hope it helps!

CodePudding user response：

Plain itertools.groupby approach:

from itertools import groupby

lst = [1, 2, 3, 6, 7, 11, 17, 18, 19]

out = []
for _, g in groupby(enumerate(lst), lambda x: x[0] - x[1]):
    out.append([v for _, v in g])

print(out)

Prints:

[[1, 2, 3], [6, 7], [11], [17, 18, 19]]