Pythonic: 找到特定长度的所有连续子序列

Question

我有一个整数列表，想要找出其中所有长度为n的连续子序列。例如：

>>> int_list = [1,4,6,7,8,9]
>>> conseq_sequences(int_list, length=3)
[[6,7,8], [7,8,9]]

我能提供的最佳翻译如下：

我所能想到的最好的方案是：

def conseq_sequences(self, li, length):
    return [li[n:n+length]
            for n in xrange(len(li)-length+1)
            if li[n:n+length] == range(li[n], li[n]+length)]

这段内容阅读起来有点吃力。有没有更易懂的Pythonic方式来实现它？

- Zakum

---

您可以假设int_list已经排序。 - Zakum

Answer 1

这里有一个更通用的解决方案，适用于任意输入可迭代对象（不仅限于序列）：

from itertools import groupby, islice, tee
from operator import itemgetter

def consecutive_subseq(iterable, length):
    for _, consec_run in groupby(enumerate(iterable), lambda x: x[0] - x[1]):
        k_wise = tee(map(itemgetter(1), consec_run), length)
        for n, it in enumerate(k_wise):
            next(islice(it, n, n), None) # consume n items from it
        yield from zip(*k_wise)

• itertools.groupby 可以在输入中找到连续的子字符串，例如 6, 7, 8, 9。它基于文档中展示如何查找连续数字的示例：

  解决方案的关键是使用由enumerate()生成的范围进行差分，以便连续整数都出现在同一组（运行）中。

• itertools.tee + zip 允许以 k-wise 的方式迭代子字符串 -- 这是对 itertools 文档中的 pairwise 配方 的一般化。

• next(islice(iterator, n, n), None) 来自那里的 consume 配方。

例子：

print(*consecutive_subseq([1,4,6,7,8,9], 3))
# -> (6, 7, 8) (7, 8, 9)

代码使用Python 3语法，如果需要可以适应Python 2。另请参阅什么是最pythonic的排序日期序列的方法？。

- jfs

---

在使用内置库方面，这对我来说看起来最优雅。为了完全理解发生的事情，我将不得不查阅您提供的链接。可读性仍然相当困难！ - Zakum

Answer 2

一种解决方案可能如下所示：

import numpy # used diff function from numpy, but if not present, than some lambda or other helper function could be used. 

def conseq_sequences(li, length):
    return [int_list[i:i+length] for i in range(0, len(int_list)) if sum(numpy.diff(int_list[i:i+length]))==length-1]

基本上，首先我从列表中获取给定长度的连续子列表，然后检查它们元素的差的总和是否等于 length - 1。

请注意，如果元素是连续的，它们的差将加起来等于 length - 1，例如对于子列表[5,6,7]，其元素的差为[1, 1]，其总和为2。

但说实话，我不确定这个解决方案是否比您的更清晰或更具Python风格。

以防您没有 numpy，可以轻松地定义diff函数如下：

def diff(l):
  '''For example, when l=[1,2,3] than return is [1,1]'''  
  return [x - l[i - 1] for i, x in enumerate(l)][1:]

- Marcin

Answer 3

使用 operator.itemgetter 和 itertools.groupby

 def conseq_sequences(li, length):
    res = zip(*(li[i:] for i in xrange(length)))
    final = []
    for x in res:
        for k, g in groupby(enumerate(x), lambda (i, x): i - x):
            get_map = map(itemgetter(1), g)
            if len(get_map) == length:
                final.append(get_map)
    return final

不使用导入。

def conseq_sequences(li, length):
    res = zip(*(li[i:] for i in xrange(length)))
    final = []
    for ele in res:
        if all(x == y+1 for x, y in zip(ele[1:], ele)):
            final.append(ele)
    return final

可以转换为列表推导式：

def conseq_sequences(li, length):
    res = zip(*(li[i:] for i in xrange(length)))
    return [ ele for ele in res if all(x == y+1 for x, y in zip(ele[1:], ele))]

- Padraic Cunningham

---

这段代码在像 [4, 1, 5, 2, 6] 这样的输入上表现不同于 OP 的代码。 - user2357112

@user2357112，我暂时脑抽了，完全忽略了连续的部分。 - Padraic Cunningham

Answer 4

 def condition (tup):
    if tup[0] + 1 == tup[1] and tup[1] + 1 == tup[2] :
        return True
    return False

 def conseq_sequence(li):
   return [x for x in map(None, iter(li), iter(li[1:]), iter(li[2:])) if condition(x)]

- Pranav Raj

---

这不符合连续性约束条件: conseq_sequence([1,4,2,7,3]) 的结果是 [[1, 2, 3], [2, 3, 4]]。然而，列表 [1,2,3] 不是我们初始列表的子列表，对于 [2,3,4]，这些数字在初始列表中以不同的顺序出现，也不是连续的。 - Zakum

抱歉，我忘记了那个条件。现在代码也会处理那个条件。 - Pranav Raj

我做了一个假设，即列表的长度将大于3，这可以很容易地进行检查。 - Pranav Raj