跨越给定数组 x 的具有固定宽度 n 的最小数组掩码集

Question

x 是 0 和 1 的 numpy 数组。 n 是满足 n <= len(x) 的任意整数。使用 x，创建 boolean 个数组的列表 y，这样：
(a) y 中的每个数组与数组 x 的大小完全相同，值为 True 或 False.
(b) n 间隙的条目应为 True，其余为 False.
(c) x 中的每个 1 应该在 y 中的一个数组中只有一个 True 值。在 y 的剩余数组中，相应的条目必须是 False.

例如：
1.如果x = np.array([1, 0, 0, 0, 1])

不同 n 的期望输出是：

n=2 : [[True, False, True, False, True]]
n=3 : [[True, False, False, True, False],
       [False, True, False, False, True]]
n=4 : [[True, False, False, False, True]]
n=5 : [[True, False, False, False, False],
       [False, False, False, False, True]]

2.如果x = np.array([1, 0, 1, 1, 1, 0, 0, 0, 0, 1])

不同 n 的期望输出是：

n=2 : [[True, False, True, False, True, False, True, False, True, False,], 
       [False, True, False, True, False, True, False, True, False, True]]
n=3 : [[True, False, False, True, False, False, True, False, False, True], 
       [False, False, True, False, False, True, False, False, True, False], 
       [False, True, False, False, True, False, False, True, False, False]]
n=4 : [[True, False, False, False, True, False, False, False, True, False], 
       [False, False, True, False, False, False, True, False, False, False], 
       [False, False, False, True, False, False, False, True, False, False], 
       [False, True, False, False, False, True, False, False, False, True]]
n=5 : [[True, False, False, False, False, True, False, False, False, False], 
       [False, False, True, False, False, False, False, True, False, False], 
       [False, False, False, True, False, False, False, False, True, False], 
       [False, False, False, False, True, False, False, False, False, True]]

请注意，实际上 x 和 n 都可以分别大到 4000 和 100 的数量级。

Answer 1

不知怎么的，我做得很低效。有人可以建议更快的解决方案吗？

Y = []
x_temp = x.copy()
y = np.zeros(len(x_temp), dtype=bool)
y[::n] = True
cnt = np.sum(x_temp)
i = 0
while (cnt > 0) and (i < n):
    if np.sum(x_temp*~y) < cnt:
        Y.append(y)
        x_temp = x_temp*~y
        cnt = np.sum(x_temp)
    y = np.roll(y, 1)
    y[:1] = False
    i+=1

Answer 2

这是一个解决方案：

y = np.zeros((n, x.size), dtype=bool)
for i in range(n):
    y[i,i::n] = True
y[np.flatnonzero((y*x).sum(-1))]

您绝对可以用更快的 numpy 方法替代循环，但我认为您的 n 不会太大，循环不应该成为瓶颈。

x = np.array([1, 0, 1, 1, 1, 0, 0, 0, 0, 1]) 和 n=5 的输出：

array([[ True, False, False, False, False,  True, False, False, False, False],
       [False, False,  True, False, False, False, False,  True, False, False],
       [False, False, False,  True, False, False, False, False,  True, False],
       [False, False, False, False,  True, False, False, False, False, True]])

跨越给定数组 x 的具有固定宽度 n 的最小数组掩码集

Minimum set of array masks with fixed width n spanning a given array x

python

algorithm

numpy

python-3.x

numpy-ndarray