algorithm - 任何人都可以帮助可能的动态编程算法

Question

首先让我为我将要表达我的问题的粗鲁方式道歉。我被另一个网站的成员推荐到这里，他告诉我我正在寻找一种动态规划算法....我的问题如下。

我正在尝试对一些数据进行排序，需要在数字中找到可能的顺序两组数据都包含以不同顺序列出的相同数字，如下例所示。

54 47 33 58 46 38 48 37 56 52 61 25 ………………第一组
54 52 33 61 38 58 37 25 48 56 47 46 ………………第二盘

在此示例中，从左到右阅读数字 54 52 61 和 25 以相同的顺序出现在两个集合中。
所以其他可能的解决方案是……

54 52 61 25
54 33 58 46
54 33 46
54 33 38 48 56
54 48 56 ….等等

虽然这可以手动完成，但我有很多事情要完成，而且我一直在犯错误。有谁知道可以输出所有可能解决方案的现有程序或脚本？

我了解 C++ 和虚拟基本程序的基本结构，应该能够在以太坊中拼凑一些东西，但老实说，自从 zx 频谱时代以来，我还没有做过任何认真的编程，所以请放轻松.然而，我的主要问题不在于程序语言本身，而是出于某种原因，我发现无法用英语对完成此任务所需的步骤进行分类，更不用说用任何其他语言了。

达西

Answer 1

听起来您正在寻找“所有常见子序列 (ACS)”，它是(更常见的)longest common subsequence problem (LCS) 的表亲.

这是一个 paper discussing ACS (尽管他们只关注计算子序列，而不是枚举)。

要提出一种算法，您应该更精确地定义所需的输出。为了争论起见，假设您希望子序列集不包含在任何更长的子序列中。那么一种算法是:

1) LCS应用DP算法，生成对齐/回溯矩阵

2) 回溯所有可能的 LCS，标记已访问的对齐位置。

3)选择矩阵中尚未标记的最大元素(最长剩余子序列)

4) 回溯，记录序列并标记访问过的比对位置。

5) 当存在未标记的对齐位置时，转到(3)

在你的情况下回溯很复杂，因为你必须访问所有可能的路径(称为“所有最长的公共(public)子序列”)。您可以找到 LCS 的示例实现 here ，这可能有助于您入门。