寻找所有可能的最长上升子序列

Question

我希望能够在给定的字符串中找到所有可能的最长递增子序列。

例如：给定字符串是qapbso

这里最长递增子序列的长度是3。 我想要找到所有长度为3的最长子序列，即 "abs"、"aps" 和 "abo"。

我正在使用动态规划，但只得到一个 LIS。我想列出所有的 LIS。

- dejavu

---

如果您正在指定所需的子序列长度，是否仍需要包含“最长可能”的概念？ - The Nail

不，我没有指定子序列的长度。这里最长上升子序列的长度是3，我只是为了清晰起见而提到它。 - dejavu

您可以在图中逐个禁用一条边（参见Benoit的答案），并保留其余部分启用。但是，是所有时间中最低效的算法之一... - The Nail

izomorphus的答案看起来还不错。得试一下。 - dejavu

Answer 1

因此，典型的动态规划解决方案将产生一个数组，在该数组中，您可以知道以给定位置i开头的最长可能子序列是什么，假设您有一个长度为n的数组，其中dp [i]存储以索引i开头的最长非递减子序列的长度。

现在，最简单的方法是使用递归打印所有的LNDSS（最长不降子序列）。首先通过选择dp中的最大值来找到LNDSS的实际长度。接下来，从dp中具有最大值的每个元素开始递归（这些可能会多于一个）。给定索引的递归应打印所有以当前索引开头且长度等于dp [i]值的序列：

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

这是c++的示例代码（希望其他语言也能理解）。我有一个名为“stack”的全局堆栈，用于保存我们已经添加的元素。它的大小为1000，假设您在LNDSS中永远不会有超过1000个元素，但这可以增加。该解决方案设计不是最佳的，但我专注于使其简单而不是完美设计。

希望这能帮到你。

- Ivaylo Strandjev

---

我在网络上找到了这个PDF文件。http://www.dei.unipd.it/~geppo/DA2/DOCS/lis.pdf请查看一下。它没有提供以相同字母结尾的最长上升子序列（LIS）。 - dejavu

我发布了一个答案，将这个放在通常的DP解决方案中供参考。 - undefined

Answer 2

在2000年，Sergei Bespamyatnikh和Michael Segal提出了一种算法，用于找到给定排列的所有最长递增子序列。该算法使用Van Emde Boas tree，时间复杂度为O(n + Kl(p))，空间复杂度为O(n)，其中n是排列p的长度，l(p)是其最长递增子序列的长度，K是这样的子序列的数量。

请参见ACM数字图书馆中的论文，或搜索“Enumerating longest increasing subsequences and patience sorting”以获取免费PDF。

- Max Mouratov

Answer 3

考虑到这张图，其中所有节点都与具有较高值且出现在您的输入字符串字母序列后面的节点相连：

你想找到从起点到终点的最长路径。如果所有段的长度都为负数-1，则等同于最短路径。

最长路径问题的参考资料：http://en.wikipedia.org/wiki/Longest_path_problem

- Benoit

---

这个应该表示为有向图吧？ :P - The Nail

这个问题不能用这种技术来解决。首先应该使用有向图。即使这样，我也想不出使用这种技术的解决方案。 - dejavu

@The Nail：用带箭头的图表替换。 - Benoit

这个图被命名为DAG，通过BFS可以找到最长的最短路径或者图的直径，不需要使用Dijekstra算法。 - Saeed Amiri

Answer 4

为了说明Ivaylo Strandjev的代码如何工作，我将其放在了通常的LIS DP解决方案中（使用Python）。注意：我的算法是用于严格递增的子序列。

def lis(a): # assumes a != []
    n = len(a)
    dp = [1 for _ in range(n)] 
    # dp[k] = length of LIS with first element a[k]
    max_length = 1
    for k in range(n - 1, -1, -1):
        result = 1
        for i in range(k + 1, n):
            if a[i] > a[k]:
                result = max(result, 1 + dp[i])
        dp[k] = result
        max_length = max(max_length, result)
    
    # printing all LISs
    st = [None for _ in range(max_length)]
    st_index = 0
    def rec(index): # credit: Ivaylo Strandjev
        nonlocal st_index, dp, a
        if dp[index] == 1:
            print("Another sequence:")
            for i in range(st_index):
                print(st[i])
        for j in range(index + 1, n):
            if dp[j] == dp[index] - 1 and a[j] >= a[index]:
                st[st_index] = a[j]
                st_index += 1
                rec(j)
                st_index -= 1
    # beginning the recursion at each valid index
    for index in range(n):
        if dp[index] == max_length:
            st_index = 1
            st[0] = a[index]
            rec(index)
    return max_length

如果你想返回LISs而不是打印它们，只需添加一个非局部列表store，并且在打印逻辑的位置写入store.append(st.copy())。

如果你想去重完全相等的LISs，使用一个非局部集合store，并且在逻辑的位置写入store.add(tuple(st))。

- Benjamin Wang