在列表中查找递增数字组

Question

目的是在给定整数列表的情况下找到一组 increasing/monotonic 个数字。结果组中的每个项目都必须比前一个项目增加 +1

给定输入：

x = [7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5]

我需要找到递增的组并实现：

increasing_numbers = [(7,8,9,10), (0,1,2,3,4,5)]

而且最终人数也在增加：

len(list(chain(*increasing_numbers)))

还有组的长度：

increasing_num_groups_length = [len(i) for i in increasing_numbers]

我尝试了以下方法来获取递增的数字：

>>> from itertools import tee, chain
>>> def pairwise(iterable): 
...     a, b = tee(iterable)
...     next(b, None)
...     return zip(a, b)
... 
>>> x = [8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6]
>>> set(list(chain(*[(i,j) for i,j in pairwise(x) if j-1==i])))
set([1, 2, 3, 4, 5, 6, 8, 9, 10, 11])
>>> len(set(list(chain(*[(i,j) for i,j in pairwise(x) if j-1==i]))))
10

但是我无法保持顺序和递增的组。

如何实现 increasing_numbers 组整数元组以及 increasing_num_groups_length？

此外，such/similar问题有名称吗？

已编辑

我想出了这个解决方案，但它非常冗长，我相信有一种更简单的方法可以实现 increasing_numbers 输出：

>>> from itertools import tee, chain
>>> def pairwise(iterable): 
...     a, b = tee(iterable)
...     next(b, None)
...     return zip(a, b)
... 
>>> x = [8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6]
>>> boundary =  iter([0] + [i+1 for i, (j,k) in enumerate(pairwise(x)) if j+1!=k] + [len(x)])
>>> [tuple(x[i:next(boundary)]) for i in boundary]
[(8, 9, 10, 11), (1, 2, 3, 4, 5, 6)]

是否有更 pythonic / 更简洁的方法来做到这一点？

另一个input/output例子：

[在]:

[17, 17, 19, 20, 21, 22, 0, 1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 28, 29, 30, 31, 32, 33, 34, 35, 36, 40]

[输出]:

[(19, 20, 21, 22), (0, 1, 2), (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14), (28, 29, 30, 31, 32, 33, 34, 35, 36)]

Answer 1

def igroups(L):
    R=[[]]
    [R[-1].append(L[i]) for i in range(len(L)) if (L[i-1]+1==L[i] if L[i-1]+1==L[i] else R.append([L[i]]))]
    return [P for P in R if len(P)>1]


tests=[[],
    [0, 0, 0],
    [7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5],
    [8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6],
    [9, 1, 2, 3, 1, 1, 2, 3, 5],
    [4,3,2,1,1,2,3,3,4,3],
    [1, 4, 3],
    [1],
    [1,2],
    [2,1]
    ]
for L in tests:
    print(L)
    print(igroups(L))
    print("-"*10)

输出以下内容：

[]
[]
----------
[0, 0, 0]
[]
----------
[7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5]
[[7, 8, 9, 10], [0, 1, 2, 3, 4, 5]]
----------
[8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6]
[[8, 9, 10, 11], [1, 2, 3, 4, 5, 6]]
----------
[9, 1, 2, 3, 1, 1, 2, 3, 5]
[[1, 2, 3], [1, 2, 3]]
----------
[4, 3, 2, 1, 1, 2, 3, 3, 4, 3]
[[1, 2, 3], [3, 4]]
----------
[1, 4, 3]
[]
----------
[1]
[]
----------
[1, 2]
[[1, 2]]
----------
[2, 1]
[]
----------

编辑我第一次尝试使用 itertools.groupby 失败了，对此深感抱歉。

Answer 2

编辑:

这是一个代码高尔夫解决方案（142 个字符）：

def f(x):s=[0]+[i for i in range(1,len(x)) if x[i]!=x[i-1]+1]+[len(x)];return [x[j:k] for j,k in [s[i:i+2] for i in range(len(s)-1)] if k-j>1]

扩展版本：

def igroups(x):
    s = [0] + [i for i in range(1, len(x)) if x[i] != x[i-1] + 1] + [len(x)]
    return [x[j:k] for j, k in [s[i:i+2] for i in range(len(s)-1)] if k - j > 1]

评论版本：

def igroups(x):
    # find the boundaries where numbers are not consecutive
    boundaries = [i for i in range(1, len(x)) if x[i] != x[i-1] + 1]
    # add the start and end boundaries
    boundaries = [0] + boundaries + [len(x)]
    # take the boundaries as pairwise slices
    slices = [boundaries[i:i + 2] for i in range(len(boundaries) - 1)]
    # extract all sequences with length greater than one
    return [x[start:end] for start, end in slices if end - start > 1]

原解:

不确定这算作 "pythonic" 还是 "not too verbose":

def igroups(iterable):
    items = iter(iterable)
    a, b = None, next(items, None)
    result = [b]
    while b is not None:
        a, b = b, next(items, None)
        if b is not None and a + 1 == b:
            result.append(b)
        else:
            if len(result) > 1:
                yield tuple(result)
            result = [b]

print(list(igroups([])))
print(list(igroups([0, 0, 0])))
print(list(igroups([7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5])))
print(list(igroups([8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6])))
print(list(igroups([9, 1, 2, 3, 1, 1, 2, 3, 5])))

输出：

[]
[]
[(7, 8, 9, 10), (0, 1, 2, 3, 4, 5)]
[(8, 9, 10, 11), (1, 2, 3, 4, 5, 6)]
[(1, 2, 3), (1, 2, 3)]

Answer 3

使用 itertools.groupby，将整数列表 L 划分到相邻的子列表中并从 L 增加连续项的问题可以用一行代码完成。尽管如此，我不知道如何将它视为 pythonic ;)

下面是带有一些简单测试的代码：

[编辑：现在子序列增加 1，我第一次错过了这一点。]

from itertools import groupby

def f(i):
    return  L[i-1]+1==L[i]


def igroups(L):
    return [[L[I[0]-1]]+[L[i] for i in I] for I in [I for (v,I) in [(k,[i for i in list(g)]) for (k, g) in groupby(range(1, len(L)), f)] if v]]

输出：

tests=[
    [0, 0, 0, 0],
    [7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5],
    [8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6],
    [9, 1, 2, 3, 1, 1, 2, 3, 5],
    [4,3,2,1,1,2,3,3,4,3],
    [1, 4, 3],
    [1],
    [1,2, 2],
    [2,1],
    [0, 0, 0, 0, 2, 5, 5, 8],
    ]
for L in tests:
    print(L)
    print(igroups(L))
    print('-'*10)


[0, 0, 0, 0]
[]
----------
[7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5]
[[7, 8, 9, 10], [0, 1, 2, 3, 4, 5]]
----------
[8, 9, 10, 11, 7, 1, 2, 3, 4, 5, 6]
[[8, 9, 10, 11], [1, 2, 3, 4, 5, 6]]
----------
[9, 1, 2, 3, 1, 1, 2, 3, 5]
[[1, 2, 3], [1, 2, 3]]
----------
[4, 3, 2, 1, 1, 2, 3, 3, 4, 3]
[[1, 2, 3], [3, 4]]
----------
[1, 4, 3]
[]
----------
[1]
[]
----------
[1, 2, 2]
[[1, 2]]
----------
[2, 1]
[]
----------
[0, 0, 0, 0, 2, 5, 5, 8]
[]
----------

一些解释。如果你 "unroll" 代码，逻辑更明显：

from itertools import groupby

def f(i):
    return L[i]==L[i-1]+1

def igroups(L):
    monotonic_states = [(k,list(g)) for (k, g) in groupby(range(1, len(L)), f)]
    increasing_items_indices = [I for (v,I) in monotonic_states if v]
    print("\nincreasing_items_indices ->", increasing_items_indices, '\n')
    full_increasing_items= [[L[I[0]-1]]+[L[i] for i in I] for I in increasing_items_indices]
    return full_increasing_items

L= [2, 8, 4, 5, 6, 7, 8, 5, 9, 10, 11, 12, 25, 26, 27, 42, 41]
print(L)
print(igroups(L))

正在输出：

[2, 8, 4, 5, 6, 7, 8, 5, 9, 10, 11, 12, 25, 26, 27, 42, 41]

increasing_items_indices -> [[3, 4, 5, 6], [9, 10, 11], [13, 14]]

[[4, 5, 6, 7, 8], [9, 10, 11, 12], [25, 26, 27]]

我们需要一个关键函数 f 来比较给定列表中的一项与前一项。现在，重要的一点是 groupby 具有键函数 f 的函数提供了一个元组 (k, S)，其中 S 表示 adjacent 来自初始列表的索引在 f 的状态不变的情况下，状态由 k 的值给出：如果 k 是 True，则 S 表示增加（通过1) items indexes else non-increasing items indices. （实际上，如上例所示，列表 S 是不完整的，缺少第一项）。

我还用一百万个项目列表进行了一些随机测试：igroups 函数 returns 始终是正确的响应，但比简单的实现慢 4 倍！越简单越容易、越快 ;)

感谢 alvas 的提问，让我很开心！

Answer 4

使用 itertools 和 numpy 的几种不同方式：

from itertools import groupby, tee, cycle

x = [17, 17, 19, 20, 21, 22, 0, 1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 28, 29, 30, 31, 32, 33, 34, 35,
     36, 1, 2, 3, 4,34,54]


def sequences(l):
    x2 = cycle(l)
    next(x2)
    grps = groupby(l, key=lambda j: j + 1 == next(x2))
    for k, v in grps:
        if k:
            yield tuple(v) + (next((next(grps)[1])),)


print(list(sequences(x)))

[(19, 20, 21, 22), (0, 1, 2), (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14), (28, 29, 30, 31, 32, 33, 34, 35, 36), (1, 2, 3, 4)]

或使用 python3 并产生自：

def sequences(l):
    x2 = cycle(l)
    next(x2)
    grps = groupby(l, key=lambda j: j + 1 == next(x2))
    yield from (tuple(v) + (next((next(grps)[1])),) for k,v in grps if k)

print(list(sequences(x)))

使用我的答案和 numpy.split 的变体：

out = [tuple(arr) for arr in np.split(x, np.where(np.diff(x) != 1)[0] + 1) if arr.size > 1]

print(out)

[(19, 20, 21, 22), (0, 1, 2), (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14), (28, 29, 30, 31, 32, 33, 34, 35, 36), (1, 2, 3, 4)]

与 ekhumoro 的回答类似：

def sequences(x):
    it = iter(x)
    prev, temp = next(it), []
    while prev is not None:
        start = next(it, None)
        if prev + 1 == start:
            temp.append(prev)
        elif temp:
            yield tuple(temp + [prev])
            temp = []
        prev = start

获取长度和元组：

def sequences(l):
    x2 = cycle(l)
    next(x2)
    grps = groupby(l, key=lambda j: j + 1 == next(x2))
    for k, v in grps:
        if k:
            t = tuple(v) + (next(next(grps)[1]),)
            yield t, len(t)


def sequences(l):
    x2 = cycle(l)
    next(x2)
    grps = groupby(l, lambda j: j + 1 == next(x2))
    yield from ((t, len(t)) for t in (tuple(v) + (next(next(grps)[1]),)
                                      for k, v in grps if k))



def sequences(x):
        it = iter(x)
        prev, temp = next(it), []
        while prev is not None:
            start = next(it, None)
            if prev + 1 == start:
                temp.append(prev)
            elif temp:
                yield tuple(temp + [prev]), len(temp) + 1
                temp = []
            prev = start

所有三个的输出都相同：

[((19, 20, 21, 22), 4), ((0, 1, 2), 3), ((4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14), 11)
, ((28, 29, 30, 31, 32, 33, 34, 35, 36), 9), ((1, 2, 3, 4), 4)]

Answer 5

如果两个连续的数字递增一个，我形成 list (group) 这些数字的 tuples。

当非递增且list（group）非空时，我将其解压并再次zip重建被zip。我使用 set 理解来消除重复数字。

  def extract_increasing_groups(seq):
    seq = tuple(seq)

    def is_increasing(a,b):
        return a + 1 == b

    def unzip(seq):
        return tuple(sorted({ y for x in zip(*seq) for y in x}))

    group = []
    for a,b in zip(seq[:-1],seq[1:]):
        if is_increasing(a,b):
            group.append((a,b))
        elif group:
            yield unzip(group)
            group = []

    if group:
        yield unzip(group)

if __name__ == '__main__':

    x = [17, 17, 19, 20, 21, 22, 0, 1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12,

         13, 14, 14, 14, 28, 29, 30, 31, 32, 33, 34, 35, 36, 40]

    for group in extract_increasing_groups(x):
        print(group)

使用集合更简单；

from collections import namedtuple
from itertools import islice, tee

def extract_increasing_groups(iterable):

    iter1, iter2 = tee(iterable)
    iter2 = islice(iter2,1,None)

    is_increasing = lambda a,b: a + 1 == b
    Igroup = namedtuple('Igroup','group, len')

    group = set()
    for pair in zip(iter1, iter2):
        if is_increasing(*pair):
            group.update(pair)
        elif group:
            yield Igroup(tuple(sorted(group)),len(group))
            group = set()

    if group:
        yield Igroup(tuple(sorted(group)), len(group))


if __name__ == '__main__':

    x = [17, 17, 19, 20, 21, 22, 0, 1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 28, 29, 30, 31, 32, 33, 34, 35, 36, 40]
    total = 0
    for group in extract_increasing_groups(x):
        total += group.len
        print('Group: {}\nLength: {}'.format(group.group, group.len))
    print('Total: {}'.format(total))

Answer 6

一个（真正）简单的实现：

x = [7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5]
result = []
current = x[0]
temp = []
for i in xrange(1, len(x)):
    if (x[i] - current == 1):
        temp.append( x[i] )
    else:
         if (len(temp) > 1):
             result.append(temp)
         temp = [ x[i] ]
    current = x[i]
result.append(temp)

你会得到[ [7, 8, 9, 10], [0, 1, 2, 3, 4, 5] ]。从那里，你可以得到递增数字的数量 [ len(x) for x in result ] 和数字的总数 sum( len(x) for x in result).

Answer 7

我认为这行得通。这并不花哨，但很简单。它构造一个起始列表 sl 和一个结束列表 el，它们的长度应该始终相同，然后使用它们索引到 x:

def igroups(x):
    sl = [i for i in range(len(x)-1)
          if (x == 0 or x[i] != x[i-1]+1) and x[i+1] == x[i]+1]

    el = [i for i in range(1, len(x))
          if x[i] == x[i-1]+1 and (i == len(x)-1 or x[i+1] != x[i]+1)]

    return [x[sl[i]:el[i]+1] for i in range(len(sl))]

Answer 8

我认为最易于维护的解决方案是让它变得简单：

def group_by(l):
    res = [[l[0]]]
    for i in range(1, len(l)):
        if l[i-1] < l[i]:
            res[-1].append(l[i])
        else:
            res.append([l[i]])
    return res

该方案不过滤掉单元素序列，但实现简单。此外，这具有 O(n) 的复杂性。如果你愿意，你也可以把它变成一个发电机。

我所说的可维护代码不是一行 300 个字符，带有一些复杂的表达式。那么也许您会想使用 Perl :)。至少你会在一年后了解该函数的行为方式。

>>> x = [7, 8, 9, 10, 6, 0, 1, 2, 3, 4, 5]
>>> print(group_by(x))
[[7, 8, 9, 10], [6], [0, 1, 2, 3, 4, 5]]

Answer 9

迟到的答案，但是一个简单的实现，概括为采用谓词，因此它不一定是递增的数字，但可以很容易地是两个数字之间的任何关系。

def group_by(lst, predicate):
    result = [[lst[0]]]
    for i, x in enumerate(lst[1:], start=1):
        if not predicate(lst[i - 1], x):
            result.append([x])
        else:
            result[-1].append(x)
    return list(filter(lambda lst: len(lst) > 1, result))

测试这个：

>>> group_by([1,2,3,4, 7, 1, 0, 2], lambda x, y: x < y)
[[1, 2, 3, 4, 7], [0, 2]]
>>> group_by([1,2,3,4, 7, 1, 0, 2], lambda x, y: x > y)
[[7, 1, 0]]
>>> group_by([1,2,3,4, 7, 1, 0, 0, 2], lambda x, y: x < y)
[[1, 2, 3, 4, 7], [0, 2]]
>>> group_by([1,2,3,4, 7, 1, 0, 0, 2], lambda x, y: x > y)
[[7, 1, 0]]
>>> group_by([1,2,3,4, 7, 1, 0, 0, 2], lambda x, y: x >= y)
[[7, 1, 0, 0]]
>>>

现在我们可以很容易地专门化这个：

>>> def ascending_groups(lst):
...     return group_by(lst, lambda x, y: x < y)
... 
>>> ascending_groups([1,2,3,4, 7, 1, 0, 0, 2])
[[1, 2, 3, 4, 7], [0, 2]]
>>>

在列表中查找递增数字组

Finding groups of increasing numbers in a list

python

list

tuples

itertools

iterable

已编辑