python - 从序列中收集子序列

Question

假设我们有以下序列:

[1, 2, 1, 1]

我们希望根据以下规则计算给定序列的所有子序列:

if s_i <= s_i+1 then s_i+1 is part of a subsequence with s_i

子序列的计算方法是从序列的第一个元素(此处为 1)开始，并将其与其右邻居(此处为 2)进行比较。如果它们应用于条件，则形成子序列。然后，2 必须与其右邻居 1 进行比较，如果它们适用，则它会加入子序列。这里他们不这样做，所以它不会加入。

此过程继续使用 2 和前一个邻居 1 的邻居，直到序列结束。之后，以类似的方式继续处理 2 的邻居。

下图显示了序列中第一个元素 1 的子序列构建过程:

因此，这个问题本质上是递归的。这是代码:

def calc(seq):
    for i in range(0, len(seq)):
          calc_subseq(i, seq)

def calc_subseq(i, seq):
       a = seq[i]
       for j in range(i+1, len(seq):
           b[j] = seq[j]
           if b <= a:
               calc_subseq(j, seq);
           else:
                #build subsequence
        #build subsequnce

现在的问题是:

计算后如何检索子序列？我使用了一个堆栈并在每次调用时传递它。此外，我还传递了一个计数器，该计数器会随着每次匹配而增加，并随着每次函数调用而传递，并在之后返回。如果不匹配，我会从堆栈中弹出与计数器计数一样多的项目。当 calc_subseq(seq) 中到达 for 循环末尾时，我会执行相同的操作。但我正在寻找更好的解决方案。

有谁知道有什么算法可以解决类似的问题吗？如果有更有效的方法那就很有趣了。我考虑了某种动态规划。

编辑:

根据要求，以下是输入序列[1,2,1,1]的所有结果:

1 (0), 2 (1)
2 (1)
2 (1)
2 (1) -> end
1 (0), 1 (2), 1 (3) 
1 (3) -> end
1 (2) -> end 
1 (0), 1(3)
1 (3) -> end
1 (0) -> end
2 (1)
2 (1)
2 (1) -> end
1 (2), 1 (3)
1 (3) -> end
1 (2) -> end
1 (3) -> end

注意:索引以(x) 形式提供。 -> end 表示已到达第二个 for 循环的末尾。因此，它显示了无法比较的最后一个元素，因为没有剩下的邻居。

Answer 1

有一个大问题。如果原始序列的长度为n，则最长的上升子序列的预期长度为O(sqrt(n))，并且该序列的每个子集都是另一个上升子序列，因此有至少其中 O(exp(sqrt(n))) 个。如果 n 即使大小适中，此类子序列的数量也会很快变得非常非常大。

因此，我将向您展示如何创建一个紧凑的树状结构，您可以从中计算上升子序列的计数，以便您可以在有限的时间内轻松生成每个答案。我没有跟踪索引，但如果您需要，该功能将很容易添加:

def rising_tree (seq):
    tree = {}
    for item in reversed(seq):
        this_count = 1 # For the subsequence of just this item
        this_next = {}
        for next_item, data in tree.items():
            if item <= next_item:
                this_count = this_count + data[0]
                this_next[next_item] = data
        tree[item] = [this_count, this_next]
    total_count = 0
    for _, data in tree.items():
        total_count = total_count + data[0]
    return [total_count, tree]

当应用于 [1, 2, 1, 1] 示例时，您将获得以下数据结构:

[   5, # How many rising subsequences were found
    {   1: [   4, # How many start with 1
               {   1: [   2,  # How many start with 1, 1
                          {   1: [   1, # How many start with 1, 1, 1
                                     {   }]}],
                   2: [   1, # How many start with 1, 2
                          {   }]}],
        2: [   1, # How many start with 2
           {   }]}]

现在我们可以将它们全部提取出来，如下所示:

def tree_sequence_iter (tree):
    items = sorted(tree[1].keys())
    for item in items:
        yield [item]
        subtree = tree[1][item]
        if (subtree[1]):
            for subseq in tree_sequence_iter(subtree):
                yield [item] + subseq


for ss in tree_sequence_iter(rising_tree([1, 2, 1, 1])):
    print(ss)

请注意，我不需要对我放入其中的 sorted 进行调用，但这样我们不仅可以得到唯一的子序列，而且实际上可以按字典顺序得到它们! (但请记住，它们可能有很多。)

如果您确实不需要生成器(并且认为我们有内存来存储它们)，我们可以简单地 list(tree_sequence_iter(rising_tree(seq))) 来生成我们的列表。