在numpy数组中，非连续元素之间的距离

Question

使用numpy或itertools，有没有一种有效的方法来确定下一个非连续元素的距离。

> import numpy as np 
> a=np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])

我希望输出结果如下:

[1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]

进一步地，我想要计算到两个新元素的距离。期望的输出结果应该是:

[3, 3, 2, 2, 2, 3, 5, 4]

因为在 a 之后有两个新元素 b 和 c 以此类推。

编辑 1 我有两个版本来查找下一个新元素:

import numpy as np                                                           
a = np.array(['a', 'b', 'b', 'c', 'd', 'a', 'b', 'b', 'c', 'c', 'c', 'd'])  

# Using numpy
u, idx = np.unique(a, return_inverse=True)                                                      
idx = np.diff(idx)                                                      
idx[idx < 0] = 1
idx[idx > 1] = 1 
count = 1
while 0 in idx:                                                                    
    idx[np.diff(idx) == count] = count+1
    count += 1                                                                                  │                                                                                           
print idx  

# Using loop
oldElement = a[0]
dist = []
count = 1
for elm in a[1:]:
    if elm == oldElement:
        count += 1
    else:
        dist.extend(range(count, 0, -1))
        count = 1
        oldElement = elm
print dist

然而，这种方法不能简单地扩展到查找2个新元素。

- imsc

---

以下数组 np.array(['a', 'a', 'a']) 的预期输出是什么？ - Cory Kramer

对于“两个新元素”的距离，['a'，'b'，'a'，'b'] 的输出应该是什么？ - shx2

@shx2，又是一个空数组[]。 - imsc

Answer 1

很遗憾，我没有一个numpy /向量化的解决方案来解决一般性问题。

这里有一个通用解决方案，适用于任何深度。您问题的第一部分对应于深度为1，第二部分对应于深度为2。此解决方案也适用于更高的深度。

显然，如果您只想解决深度为1的情况，那么可以提出一个简单得多的解决方案。但是，对于这个问题，普遍性增加了复杂性。

from itertools import groupby, chain, izip

ilen = lambda it: sum(1 for dummy in it)

def get_squeezed_counts(a):
    """
    squeeze a sequence to a sequnce of value/count.
    E.g. ['a', 'a', 'a', 'b'] --> [['a',3], ['b',1]]
    """
    return [ [ v, ilen(it) ] for v, it in groupby(a) ]

def get_element_dist(counts, index, depth):
    """
    For a given index in a "squeezed" list, return the distance (in the
    original-array) with a given depth, or None.
    E.g.
    get_element_dist([['a',1],['b',2],['c',1]], 0, depth=1) --> 1     # from a to first b
    get_element_dist([['a',1],['b',2],['c',1]], 1, depth=1) --> 2     # from first b to c
    get_element_dist([['a',1],['b',2],['c',1]], 0, depth=2) --> 3     # from a to c
    get_element_dist([['a',1],['b',2],['c',1]], 1, depth=2) --> None  # from first b to end of sequence
    """
    seen = set()
    sum_counts = 0
    for i in xrange(index, len(counts)):
        v, count = counts[i]
        seen.add(v)
        if len(seen) > depth:
            return sum_counts
        sum_counts += count
    # reached end of sequence before finding the next value
    return None

def get_squeezed_dists(counts, depth):
    """
    Construct a per-squeezed-element distance list, by calling get_element_dist()
    for each element in counts.
    E.g.
    get_squeezed_dists([['a',1],['b',2],['c',1]], depth=1) --> [1,2,None]
    """
    return [ get_element_dist(counts, i, depth=depth) for i in xrange(len(counts)) ]

def get_dists(a, depth):
    counts = get_squeezed_counts(a)
    squeezed_dists = get_squeezed_dists(counts, depth=depth)
    # "Unpack" squeezed dists:
    return list(chain.from_iterable(
        xrange(dist, dist-count, -1)
        for (v, count), dist in izip(counts, squeezed_dists)
        if dist is not None
    ))

print get_dists(['a','b','b','c','d','a','b','b','c','c','c','d'], depth = 1)
# => [1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]
print get_dists(['a','a','a'], depth = 1)
# => []
print get_dists(['a','b','b','c','d','a','b','b','c','c','c','d'], depth = 2)
# => [3, 3, 2, 2, 2, 3, 5, 4]
print get_dists(['a','b','a', 'b'], depth = 2)
# => []

对于Python3，请将xrange->range和izip->zip进行替换。

- shx2

---

谢谢。这看起来非常有前途。 - imsc

Answer 2

这是我尝试计算一个元素距离的代码。

import numpy as np
a=np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])
out = []
for i in range(len(a)):
    count = 0
    for j in range(len(a) - i):
        if a[i] != a[j+i]:
            out.append(count)
            break
        else:
            count += 1

结果

>>> out
[1, 2, 1, 1, 1, 1, 2, 1, 3, 2, 1]

- Cory Kramer

Answer 3

如果没有太多独特的元素，这里有一个向量化的想法。它可能不够通用，只能解决你的问题序列a :)（我一直在尝试数组，直到它起作用）。最后的while循环应该是可以优化的：

import numpy as np
a = np.array(['a','b','b','c','d','a','b','b','c','c','c','d'])

aa = a[:, np.newaxis] == np.unique(a)
aaa = np.cumsum(aa[::-1], axis=0)[::-1] * aa

# this is where it gets messy

negative_jump = True
while negative_jump:
    d = np.diff(aaa, axis=0)
    correction = (d + 1) * (d < -1)
    negative_jump = (correction != 0).any()
    aaa[:-1] += correction
result = aaa[:-1].sum(axis=1)

说明：在循环之前查看aaa。它将包含远离0的数字。在这个数据视图中，必须确保从一行到另一行的递减永远不会小于< -1 。如果是，则上面的数字太大了。循环将其逐步减少，直到-1或0。再次强调，这并不是最优解，可以做得更好。

- eickenberg