在Python列表中查找距离相近的数字

Question

我在Python里有一串数字，长得像这样：

a = [87, 84, 86, 89, 90, 2014, 1000, 1002, 997, 999]

我想保留那些相互之间差不多的数字，也就是相差不超过7的数字，其他的就不要了。请问在Python里有没有简单的方法可以做到这一点？我听说过列表过滤的方法，但不太确定怎么用它来实现我的需求。

我刚开始学Python。

更新

我希望最后的结果是[84, 86, 87, 89, 90]和另一个列表[997, 999, 1000, 1002]。我想要的是这些数字的连续序列，而不是那些离群的数字。希望这样说能让你明白。

Answer 1

假设我们有一个列表 aa = [87, 84, 86, 89, 90, 2014, 1000, 1002, 997, 999]。

aa = sorted(aa)
aa
[84,86,87,89,90,997,999,1000,1002,2014]

要找出相邻数字之间的差异，可以用 ad = np.ediff1d(aa) 这个方法。

ad
array([2, 1, 2, 1, 907, 2, 1, 2, 1012])

如果想要去掉超出某个范围的数字的索引，可以用 np.where(ad > rng)[0] + 1，这里 rng = 7 是我们想要保留的范围：

np.where(ad > 7)[0] + 1
array([5, 9])

接下来，我们可以根据这些索引把数组分割成需要的小数组，方法是 np.split(aa, np.where(ad > rng)[0] + 1)。所以，这个功能是：

def splitarr(aa,rng):
    ad = np.ediff1d(aa)
    return np.split(aa, np.where(ad > rng)[0] + 1)

splitarr(aa, 7)    
[array([84, 86, 87, 89, 90]), array([ 997,  999, 1000, 1002]), array([2014])]

我们可以通过过滤器来设置允许的序列长度：

np.where(np.fromiter(map(len, splarr), dtype=int) >= lim)[0]

这里 splarr = np.split(aa, np.where(ad > rng)[0] + 1) 会返回允许长度的数组的索引。用 map(len, splarr) 可以得到列表 splarr 中所有数组的长度；np.fromiter() 则把 map 转换成 numpy 格式，以便进行 >= lim 的比较。这里的 lim 是数组长度的阈值，只有这个长度及以上的才算可以。所以，最终的功能是：

def splitarr(aa,rng,lim):
    splarr = np.split(aa, np.where(np.ediff1d(aa) > rng)[0] + 1)
    return [splarr[i] for i in np.where(np.fromiter(map(len, splarr), dtype=int) >= lim)[0]]

splitarr(aa, 7, 2)
[array([84, 86, 87, 89, 90]), array([ 997,  999, 1000, 1002])]
splitarr(aa,7,1)
[array([84, 86, 87, 89, 90]), array([ 997,  999, 1000, 1002]), array([2014])] 
splitarr(aa, 1, 1)
[array([84]), array([86, 87]), array([89, 90]), array([997]), array([ 999, 1000]), array([1002]), array([2014])]
splitarr(aa,1,2)
[array([86, 87]), array([89, 90]), array([ 999, 1000])]
splitarr(aa,2,2)
[array([84, 86, 87, 89, 90]), array([ 997,  999, 1000, 1002])]

关于“最佳答案”下的评论：这个方法只适用于范围为7的情况，对于其他值是不正确的。

Answer 2

a = [87, 84, 86, 89, 90, 2014, 1000, 1002, 997, 999]
temp=a[0]
result=[]
temp1=[]
counter =len(a)

for i in a:
    if i in range(temp-7,temp+7):
        temp1.append(i)
        if counter==1:
            result.append(temp1)
    else:
        if temp1:
            result.append(sorted(temp1))
        temp1=[]
        temp=i
    counter=counter-1
print result

当然可以！请把你想要翻译的内容发给我，我会帮你把它变得简单易懂。

Answer 3

如果你的问题允许传递关系，也就是说，只要某个元素离组内的任何元素最多7个单位远，它就算在这个组里，那么这就像是一个图论的问题。更具体一点，你需要找到所有的连通分量。

这个问题其实用递归算法解决起来很简单。你首先需要创建一个字典，每个键对应一个元素，而每个值则是一个列表，里面包含所有离这个元素最多7个单位远的元素。以你的例子来说，可能会像这样：

for element in elements:
    connections[element] = []
    visited[element] = False
    for another in elements:
        if abs(element - another) <= limit:
            connections[element].append(another)

这样你就会得到类似下面的结果：

{
    84: [86, 87, 89, 90],
    86: [84, 87, 89, 90],
    ...
    997: [999, 1000, 1002]
    ...
    2014: []
}

接下来，你需要写一个递归函数，这个函数接收一个元素和一个列表作为输入，只要能找到一个离当前元素最多7个单位远的元素，它就会继续把这个元素加到列表里。

def group_elements(element, group):
    if visited[element]:
        return
    visited[element] = True
    group.append(element)
    for another in connections[element]:
        group_elements(another, group)

在代码的某个地方，你还需要记住哪些元素你已经访问过，以确保不会进入无限循环。

visited = {}

你需要对列表中的每个元素都调用这个函数。

groups = []
for element in elements:
    if not visited[element]:
        group = []
        group_elements(element, group)
        groups.append(group)
print group

这段代码应该会对你的输入产生以下输出：

[[87, 84, 86, 89, 90], [2014], [1000, 1002, 997, 999]]

Answer 4

对于这种问题，我通常会先去看看 Python的itertools模块。我在代码中使用的 pairwise 函数可以在 more-itertools模块 中找到。

from more_itertools import pairwise
results = []
chunk = []
a = [87, 84, 86, 89, 90, 2014, 1000, 1002, 997, 999]
a.sort()
for v1, v2 in pairwise(a):
    if v2 - v1 <= 7:
        chunk.append(v1)
    elif chunk:
        chunk.append(v1)
        results.append(chunk)
        chunk = []
print(results)
[[84, 86, 87, 89, 90], [997, 999, 1000, 1002]]

我没有测试一些特殊情况，所以使用时要小心哦 :)

Answer 5

这是一个算法问题，试试这个：

def get_blocks(values):
    mi, ma = 0, 0
    result = []
    temp = []
    for v in sorted(values):
        if not temp:
            mi = ma = v
            temp.append(v)
        else:
            if abs(v - mi) < 7 and abs(v - ma) < 7:
                temp.append(v)
                if v < mi:
                    mi = v
                elif v > ma:
                    ma = v
            else:
                if len(temp) > 1:
                    result.append(temp)
                mi = ma = v
                temp = [v]
    return result

a = [87, 84, 86, 89, 90, 2014, 1000, 1002, 997, 999]
print get_blocks(a)

输出结果：

[[84, 86, 87, 89, 90], [997, 999, 1000, 1002]]