gpt4 book ai didi

python - 从序列中收集子序列

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:53:31 25 4
gpt4 key购买 nike

假设我们有以下序列:

[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 的子序列构建过程:

Algorithm

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

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循环已经结束。因此,它显示了最后一个无法比较的元素,因为没有剩下的邻居。

最佳答案

有一个大问题。如果原始序列的长度为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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com