计算数组的相邻幂集

Question

但在我的例子中，我只需要相邻部分的幂集。

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

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

我正在努力实现这个...

非常感谢功能性解决方案（最终递归）。

Answer 1

可以使用滑动windows来解决这个问题：

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 的滑动 window 并复制滑动 [=33] 的内容来生成特定长度 l 的所有子数组=] 到结果，同时在数组上移动。

Answer 2

递归求解在Python-

st = set()

arr = [1, 2, 3]

res = list()

def power_set(i, j):
    if i == j:
        return
    if (i, j) not in st:
        res.append(arr[i : j])
    power_set(i, j - 1)
    power_set(i + 1, j)
    st.add((i, j))

power_set(0, len(arr))

print(res)

输出-

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

Answer 3

非空范围看起来像 xs[i:j] 其中 i<j.

您可以为此使用嵌套循环：

def adj_powerset(xs):
    for i in xrange(len(xs)):
        for j in xrange(i, len(xs)):
            yield xs[i:j+1]

print list(adj_powerset([1, 2, 3]))

输出：

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

计算数组的相邻幂集

Calculate Adjacent Powerset of an array

algorithm

powerset