在 python 数组中查找没有子集的唯一集

Question

我有一个数据集需要输出布尔类型的数据，只有 1 和 0，表示真或假。我正在尝试解析我处理过的简单数据集以在 numpy 数组中查找信息子集，该数组在一个方向上大约有 100,000 个元素，在另一个方向上大约有 20 个元素。我只需要沿 20 轴搜索，但我需要对 100,000 个条目中的每一个都执行此操作并获得我可以映射的输出。

我已经生成了一个由零组成的这种大小的数组，目的是简单地将匹配索引指示符标记为 1。一个主要问题是，如果我找到一个长集合（我正在使用长集到小集），我不需要在其中包含任何较小的集。

样本： [0,0,1,1,1,1,1,0,0,1,1,1,0,0,0,1,0,1]

我需要在这里找到 1 组 5，从索引 2 开始，还有 1 组 3，从索引 9 开始，而不是 return 5 组的任何子集，就像它是一组 4 人或一组 3 人，因此留下所有已经涵盖的值的结果。即对于 3 组，索引 2、3、4、5 和 6 都将保持为零。它不需要太高效，我不在乎它是否搜索，我只需要不保留结果。

目前我正在使用基本上像这样的代码块进行简单搜索：

values = numpy.array([0,1,1,1,1,1,0,0,1,1,1])
searchval = [1,2]
N = len(searchval)
possibles = numpy.where(values == searchval[0])[0]
print(possibles)
solns = []
for p in possibles:
    check = values[p:p+N]
    if numpy.all(check == searchval):
        solns.append(p)
print(solns)

我一直在绞尽脑汁试图想出一种方法来重组此代码或类似代码以产生所需的结果。最终目标是搜索 9 组到 3 组，并有效地具有 1s 和 0s 的矩阵，指示索引是否有一个组开始，只要我们想要。

希望有人能指出我做这项工作所缺少的东西。谢谢！

Answer 1

是这样的吗？

from collections import defaultdict

sample = [0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1]

# Keys are number of consecutive 1's, values are indicies
results = defaultdict(list)
found = 0

for i, x in enumerate(samples):
    if x == 1:
        found += 1
    elif i == 0 or found == 0:
        continue
    else:
        results[found].append(i - found)
        found = 0

if found:
    results[found].append(i - found + 1)

assert results == {1: [15, 17], 3: [9], 5: [2]}

Answer 2

使用more_itertools，第三方库(pip install more_itertools)：

import more_itertools as mit


sample = [0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1]

groups = [list(c) for c in mit.consecutive_groups((mit.locate(sample)))]
d = {group[0]: len(group) for group in groups}
d
# {2: 5, 9: 3, 15: 1, 17: 1}

此结果为"At index 2 is a group of 5 ones. At group 9 is a group of 3 ones,"等

详情

more_itertools.locate 默认查找真实项的索引。
more_itertools.consecutive_groups 将连续的数字组合在一起。
结果是（起始索引，长度）对的字典。

作为dictionary，您可以提取不同类型的信息：

>>> # List of starting indices
>>> list(d)
[2, 9, 15, 17]

>>> # List indices for all lonely groups
>>> [k for k, v in d.items() if v == 1]
[15, 17]

>>> # List indices of groups greater the 2 items
>>> [k for k, v in d.items() if v > 1]
[2, 9]

Answer 3

这是一个 numpy 解决方案。我正在使用一个小示例进行演示，但它很容易扩展（20 x 100,000 在我相当普通的笔记本电脑上需要 25 毫秒，请参阅本文末尾的计时 post）：

>>> import numpy as np
>>> 
>>> 
>>> a = np.random.randint(0, 2, (5, 10), dtype=np.int8)
>>> a
array([[0, 1, 0, 0, 1, 1, 0, 0, 0, 0],
       [0, 1, 1, 0, 1, 0, 1, 0, 0, 0],
       [1, 0, 1, 1, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1, 1, 1, 1, 0, 0]], dtype=int8)
>>> 
>>> padded = np.pad(a,((1,1),(0,0)), 'constant')
# compare array to itself with offset to mark all switches from
# 0 to 1 or from 1 to 0
# then use 'where' to extract the coordinates
>>> colinds, rowinds = np.where((padded[:-1] != padded[1:]).T)
>>> 
# the lengths of sets are the differences between switch points
>>> lengths = rowinds[1::2] - rowinds[::2]
# now we have the lengths we are free to throw the off-switches away
>>> colinds, rowinds = colinds[::2], rowinds[::2]
>>> 
# admire
>>> from pprint import pprint
>>> pprint(list(zip(colinds, rowinds, lengths)))
[(0, 2, 1),
 (1, 0, 2),
 (2, 1, 2),
 (2, 4, 1),
 (3, 2, 1),
 (4, 0, 5),
 (5, 0, 1),
 (5, 2, 1),
 (5, 4, 1),
 (6, 1, 1),
 (6, 3, 2),
 (7, 4, 1)]

时间安排：

>>> def find_stretches(a):
...     padded = np.pad(a,((1,1),(0,0)), 'constant')
...     colinds, rowinds = np.where((padded[:-1] != padded[1:]).T)
...     lengths = rowinds[1::2] - rowinds[::2]
...     colinds, rowinds = colinds[::2], rowinds[::2]
...     return colinds, rowinds, lengths
... 
>>> a = np.random.randint(0, 2, (20, 100000), dtype=np.int8)
>>> from timeit import repeat
>>> kwds = dict(globals=globals(), number=100)
>>> repeat('find_stretches(a)', **kwds)
[2.475784719004878, 2.4715258619980887, 2.4705517270049313]

在 python 数组中查找没有子集的唯一集

Finding unique sets without subsets in python array

python

arrays

numpy

list

matching