假设我们有以下顺序:

[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的子序列构建过程:
python - 从序列中收集子序列-LMLPHP
因此,问题本质上是递归的。代码如下:
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 (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

注:索引以[1,2,1,1]格式提供(x)表示已到达第二个for循环的结尾。因此,它显示了最后一个无法比较的元素,因为没有邻居了。

最佳答案

有一个大问题如果原始序列的长度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)))来生成我们的列表。

关于python - 从序列中收集子序列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52898889/

10-16 09:25