algorithm - 计算数组的相邻幂集

Question

互联网是 full of powerset algorithms .

但就我而言，我只需要相邻部分的幂集。

例如。来自:[1, 2, 3]，我需要得到:

adjacentPowerset([1, 2, 3]) = [[1, 2, 3], [1, 2], [2, 3], [1], [2], [3]];
// Without [1, 3]

我正在努力实现这一点......

功能解决方案将不胜感激(最终递归)。

Answer 1

可以使用滑动窗口来解决这个问题:

python 代码:

def adjacent_powerset(arr):
    result = []

    #loop over all possible lengths of subarrays
    for i in range(1, len(arr) + 1):  
        #loop over all possible starting indices of subarrays of length i
        for j in range(1, len(arr) - i + 1):
            #store subarray at position j with length i in the powerset
            result.append(arr[j:j+i])

    return result

试运行:

print adjacent_powerset([1, 2, 3, 4])

产生

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

如果您喜欢从最大到最小子集的顺序，则必须替换此行:

for i in range(1, len(arr) + 1):

通过

for i in range(len(arr) , 0, -1):

基本思想是，可以使用长度为 l 的滑动窗口生成特定长度 l 的所有子数组，并将滑动窗口的内容复制到结果，同时在数组上移动。