打印所有连续子阵列

Question

我想编写一个递归函数，将所有连续的子数组添加到一个列表中。 该功能可以工作，但存在一些重复。我想知道是否有办法避免这种情况

def numSubArray(array, result):
    if len(array) == 0:
        return []
    result.append(array)
    numSubArray(array[1:], result)
    numSubArray(array[:-1], result)
    return result

Answer 1

您有一个数组作为输入，希望返回一个包含该数组中所有值的列表，最好使用递归函数

我想你想要这个：

new_list = []
def array_to_list(arr): 
     for i in arr: 
         if isinstance(i,list) or isinstance(i,array.array): 
             array_to_list(arr) 
         else: 
             new_list.append(i)
a = arr.array('d',  [1.1, 3.5, 4.5])
array_to_list(a)
print(new_list)

最后一行将打印列出的阵列

Answer 2

您的代码似乎生成以下内容，以生成非空array的所有子序列：

1. array（也就是说，包括array中的第一项和最后一项的所有子序列）
2. array[1:]的所有子序列（即，所有不但的子序列包括array中的第一项）
3. array[:-1]的所有子序列（即，所有不但的子序列包括array中的最后一项）

因此，复制的来源是明确的：任何在array中既没有第一项也没有最后一项的子序列都将被计数两次（在任何给定的调用中，这意味着array越长，可以获得的副本就越多）

希望解决方案也很清楚；删除#1（下面将介绍它），然后

• 替换#3将所有不的子序列包括^{中的第一项，或者
• 将#2替换为包含^{中最后一项的所有子序列

Answer 3

解决方案1。强力递归并删除重复项

您可以使用set消除重复。
但是您不能对list进行set，因为list是不可散列的。
为了提高效率，您可以先收集索引对，然后切片：

def num_sub_array(array):
    return [
        array[i:j] for i, j in build_pair_set(0, len(array))
    ]


def build_pair_set(start: int, end: int) -> set:
    return set() if start == end else (
        {(start, end)}
        | build_pair_set(start + 1, end)
        | build_pair_set(start, end - 1)
    )


print(sorted(num_sub_array([1, 2, 3, 4])))

输出：

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

---

解决方案2。无冗余递归

def num_sub_array(array):
    if not array:
        return []
    return [array[i:] for i in range(len(array))] + num_sub_array(array[:-1])


print(sorted(num_sub_array([1, 2, 3, 4])))

输出：

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

---

实际上，解决方案2的num_sub_array有一个尾部递归。所以您可以将其更改为循环

解决方案3。循环

def num_sub_array(array):
    return [
        array[i:j]
        for i in range(len(array))
        for j in range(i + 1, len(array) + 1)
    ]


print(sorted(num_sub_array([1, 2, 3, 4])))

输出：

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

---

我用sorted来比较两种方法。这是没有必要的