时间戳

首页 > 解决方案 > 从集合中获取包含给定子集的所有大小为 N 的序列的算法

algorithm - 从集合中获取包含给定子集的所有大小为 N 的序列的算法

问题描述

更具体地说，我们想要输出的序列可以使输入子集中的元素与输入子集中的元素的顺序不同。

示例：假设我们有一个集合 {1, 9, 1, 5, 6, 9, 0 , 9, 9, 1, 10} 和一个输入子集 {9, 1}。我们希望找到包含输入子集的所有元素的所有大小为 3 的子集。这将返回集合 {1, 9, 1} , {9, 1, 5}, {9, 9, 1}, {9, 1, 10}。

当然，具有最低复杂度的算法是首选。

编辑：用更好的术语编辑。另外，这是我考虑的伪代码：

1. For each sequence s in the set of size n, do the following: 
    2. Create a list l that is a copy of the input subset i. 
    3. j = 0
    4. For each element e in s, do the following: 
        5. Check if it's in i. 
        If it is, remove that element from l. 
        6. If l is empty, add s to the sequences to return,
        skip to the next sequence (go to step 1)
        7. Increment j. 
        8. if j == n, go to the next sequence (go to step 1)

这是我想出的，但是由于我们考虑每个序列而没有任何以前扫描过的序列的记忆，这需要非常多的时间。我真的不知道如何实现这样的内存，这对我来说都是全新的。

标签： algorithmsearchtime-complexity

解决方案

您可以简单地找到该子集的所有出现，然后生成包含该组合的所有列表。

以python为例：

def get_Allsubsets_withSubset(original_list, N , subset):
    subset_len = len(subset)
    list_len = len(original_list)
    index_of_occurrence = []
    overflow = N - subset_len

    for index in range(len(original_list)-len(subset)):
        if original_list[index: index +len(subset)] == subset:
            index_of_occurrence.append(index)
    final_result = []
    for index in index_of_occurrence:
        for value in range(overflow+1):
            i = index - value
            final_result.append(original_list[i:i+N])
    return final_result

它并不美丽，但我会说它是一个开始

推荐阅读