我有一个与经典的“最长公共子序列”问题有关的问题。我将给出问题的背景，但如果你愿意，你可以跳到下面的公式

让我们把细菌染色体上的基因想象成一根绳子上的珠子——原子的、独特的物体，有一个顺序。我故意忽略了一些东西，想看一个简化的模型。所以假设染色体是区间 [1,1000]，有 1000 个基因，区间中的每个整数都有一个。

现在假设我有一组 100 条染色体，每条染色体来自群体中的不同个体，每条染色体都有 1000 个基因，但允许顺序不同。

换句话说，我有 100 种不同的整数 1..1000 排列。让我们看一个例子

1 2 3 4 5 6 7 8 9 10

1 8 9 2 3 4 5 6 7 10

1 4 3 2 7 8 9 10 5 6

1 4 3 2 10 8 9 5 6 7

当我看到这些时，我看到了两件事。首先，前两个都包含 1 2 3 4 5 6 7 10 作为子序列。其次，最后两个包含 1 4 3 2 8 9 5 6

我想构建一个算法，用于将排列列表拆分为这样的子集，这样在子集中，所有排列都包含一个公共子序列。一个简单的解决方案当然是使每个排列成为大小为 1 的子集，所以我真正想要的是最小化子集的数量，并最大化子序列的长度。

以前有很多关于找到固定集合的最长公共子序列（https://en.wikipedia.org/wiki/Longest_common_subsequence_problem）的工作，但我找不到任何解决如何分割字符串以最大化长度的工作子集中的公共子序列。

有谁知道这是否也是一个经典/已解决的问题？

PS我在mathOverflow上发布了一个（稍微不太好的）版本，组织者把我送到了这里。