numpy 在一个不连续的阵列上可以容纳多少个长度为N的窗口

xxe27gdn  于 2023-06-23  发布在  其他
关注(0)|答案(1)|浏览(118)

给定一个所有值都为1或0的任意数组,有多少个(编辑:长度为N的非重叠窗口的最大数目是多少?窗口必须以1(True)值为中心。(编辑:假设N是奇数)。窗口的两侧可以是0,数组两端的值可以算作有效值。如果可能的话,我更喜欢使用numpy和/或pandas的答案。
真实世界的用例是安排会议,这样它们就不会重叠。该数组可以表示一年中的天数,1表示可用于举行会议的天数,并且有一个规则,即会议必须在两天之间安排。
示例:

array_1 = [1, 0, 0, 1, 0, 0, 1, 0]

array_2 = [0, 0, 0, 1, 1, 1, 0, 0]


count_windows(array=array_1, window_size=3)

out:3解释:按索引显示窗口:[0, 1], [2, 3, 4], [6, 7, 8]

count_windows(array=array_2, window_size=3)

out:1解释:按索引显示窗口:[2, 3, 4]以索引5为中心的窗口将包括索引4,索引4将与以索引3为中心的窗口重叠

bvjxkvbb

bvjxkvbb1#

我有一个很可能是非最优的解决方案(即它不最大化窗口的数量,而是选择第一个有效窗口)。它还有一个嵌套的for循环,所以这个解决方案对于大型数组来说会很慢。也许有人可以用这个答案找到一个矢量化的解决方案。
本质上,我的解决方案找到值为1的索引(使用np.where),然后在每个点周围创建一个索引窗口(我假设window_size总是奇数)。然后检查每个窗口之间的重叠(使用np.isin),如果没有重叠,则保留该窗口。最后,它删除可能添加到结果列表中的任何可能的重复行(使用np.unique),并消除负数(当1接近开始或结束时,会发生负索引)。返回值是一个Python。

import numpy as np

def count_windows(arr, window_size):
    assert window_size % 2, "window_size is not odd."
    
    a = np.where(arr)[0]
    n = (window_size - 1)//2
    b = np.stack(a+np.arange(-n, n+1)[:,None], axis=1)
    windows = [b[0]]
    for i in range(b.shape[0]):
        for j in range(i+1, b.shape[0]):
            if ~np.isin(b[i], b[j]).any():
                windows.append(b[j])
                
    c = np.unique(windows, axis=0)
    return [row[row >= 0].tolist() for row in c]
    

array_1 = [1, 0, 0, 1, 0, 0, 1, 0]
array_2 = [0, 0, 0, 1, 1, 1, 0, 0]

print(count_windows(array_1, 3))  # [[0, 1], [2, 3, 4], [5, 6, 7]]
print(count_windows(array_2, 3))  # [[2, 3, 4]]

相关问题