algorithm - 查找子序列序列的算法

Question

序列 [1,2,3] 考虑。该序列有以下 6 种不同的序列：[1]and [2]and [3] and [1,2] and [2,3] and [1,2,3]

笔记！初始序列的长度最多可达 100 位。请帮我。如何制作以下序列？我喜欢更多地研究这种算法。请告诉我这种算法的名称。

Answer 1

这是打印所有子序列的 ac 代码。算法使用嵌套循环。

    #include<stdio.h>

  void seq_print(int A[],int n)
{
    int k;
    for(int i =0;i<=n-1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            k=j;
            while(k<=i)
            {
                printf("%d",A[k]);
                k++;

            }
            printf("\n");
        }
}

}

void main()
{
    int A[]={1,2,3,4,5,6,7,8,9,0};
    int n=10;
    seq_print(A,n);

}

Answer 2

它被称为幂集（在您的情况下，不包括空集）。

要构建幂集，请从其中包含空集的集开始；然后对于输入集中的每个项目，扩展幂集，其中包含迄今为止累积的所有子集，包括当前项目（在 Python 中）：

def powerset(lst):
    S = [[]]
    for item in lst:
        S += [subset + [item] for subset in S]
    return S

例子：

print(powerset([1, 2, 3]))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

为了避免一次生成所有子集，可以使用递归定义：

• 空集的幂集是其中包含空集的集合
• 具有项目的n集合的幂集包含来自具有项目的集合的幂集的所有子集以及包含第-项n - 1的所有这些子集n。

def ipowerset(lst):
    if not lst: # empty list
        yield []
    else:
        item, *rest = lst
        for subset in ipowerset(rest):
            yield subset
            yield [item] + subset

例子：

print(list(ipowerset([1, 2, 3])))
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

生成幂集的另一种方法是为从零到输入集（配方r）大小的所有子序列（组合）生成 -length 子序列（组合）：ritertools

from itertools import chain, combinations

def powerset_comb(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

例子：

print(list(powerset_comb([1, 2, 3])))
# -> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]

另请参阅通过集合进行组合的好方法是什么？.

Answer 3

您的问题可以简化为组合问题。stackoverflow 中已经有很多解决方案。你可以检查一下，它可能对你有用。