我正在搜索one由以下子集Sp1...pn组成的排列P。S由"标签"L定义。L1...Lk.其中L包含pi...pj. 其中P的反数最多k-1递减的相邻元素。k <= n.
例：
n := 4
k := 2
L1 := 1,2
L2 := 3,4
L := L1,L2,L1,L2
S := 1324,1423,2314,2413
一种解决方案是P := 1342
不会P := 3142任何解决方案，因为减少的相邻元素是2，但只有最大1允许，因为k =2。
因此存在一种算法来查找由L定义的SP？
目前我使用蛮力来计算一个排列P，但它变得非常快无法使用缓慢。
所以L1, ..., Lk每个元素都是一组连续的元素。 在每一个地方，我们看到L定义中的Li, Lj，有三件事之一是正确的：
i < j在这种情况下，- 它是升序的。
- 它可以是上升或下降。
- 它必须是下降的。
i = j在这种情况下，i > j在这种情况下，通过计算情况 3 为真的位置数，我们得到了L定义中已经存在的最小数量的降序元素。
接下来，对于每个Li，我们都有一个模式，我们可以用len(Li)-1;和,写下来，其中;表示在Li的两个成员之间存在其他Lj元素，,表示Li元素是相邻的，因此元素的顺序可能导致下降。我们想知道，"对于Li内每个可能的下降次数，有多少个Li排列具有该下降次数？
我们将考虑按如下方式构建排列：
The first element goes at position 0.
The second element goes to position 0 or 1. (If at 0, the first element is moved.)
The third element goes to position 0, 1, or 2.
etc
下降是指下一个元素小于前一个元素，在与,匹配的过渡处。
我们实际上需要以下数据结构供以后使用：
cache[Li] gives:
by how many elements are chosen:
by the last element chosen:
by the number of descents we will add:
how many ways of finishing this permutation
因此，我们可以编写一个递归函数，该函数采用：
Li的模式 .- 选择了多少个元素。
- 上次选择的索引。
然后，它返回一个字典，将下降映射到完成Li排列的方法计数。
记住这一点，我们得到我们想要的数据结构。
现在我们将重复这个想法。 我们希望：
cache2[i] gives:
by number of descents to use:
how many permutations of L[i], L[i+1], ..., L[k] meet it.
同样，我们可以使用cache编写一个递归函数来计算它，我们可以记住它以获得cache2。
现在我们可以逆转这个过程。
- 我们知道有多少血统来自
L的定义。 - 我们知道
cache2[1]剩余下降的分布，因此我们可以随机选择有多少下降将满足我们的条件L1...Lk。 - 对于
L1...Lk，我们可以查看cache[L1][1][0]和cache2[i+1]，以正确的概率计算出Li内将有多少次下降。 - 对于每个
Li我们可以查看我们想要结束的下降次数、它的模式以及cache2[Li]，以找出以正确模式结束的随机插入序列。第一个插入始终在0处。之后，您始终知道大小，最后一个插入的位置以及还剩下多少下降。 因此，对于每个可能的下一个插入，您确定它是否算作下降(查看两种模式，以及它是否在最后一次插入之前)，以及从那里完成的方法数量。然后，您可以随机选择具有正确可能性的下一个插入。 - 对于每个
Li我们可以按顺序将插入的模式转换为值列表。(我将进一步解释此步骤。 - 现在，我们可以遵循
L模式并填写所有值。
现在对于第 5 步，让我们用聊天中的示例进行说明。 假设L2 = [4, 5, 6]和我们想出的插入模式是[0, 1, 0]. 我们如何计算值的排列？
首先，我们进行插入：
[1]
[1, 2]
[3, 1, 2]
这表示第一个元素(4)到第三个，第二个(5)到第一个，第三个(6)到第二个。 所以我们对L2的排列是[5, 6, 4].
这将需要编写大量代码。但它将是多项式的。 具体来说，如果m是最常见标签的计数，则cache的总大小最多为O(k m^2)。由于记忆，每个条目都需要O(m)来计算。除此之外，其他一切都很小。 所以总空间是O(k m^2)，时间是O(k m^3).