用 DI 序列排列排列

Question

我想通过长度给定的排列子集进行排序和取消排序。子集定义如下：

排列长度 4 的示例：

我们有输入位串长度 3（总是排列长度 - 1）

010

0表示连续2个元素I递增。

1表示连续2个元素D递减。

对于此位串，存在具有以下排列的子集：1324、1423、2314、2413、3412

我要排序和取消排序的位串定义的排列子集？给定的位串是否有算法来做到这一点？

Answer 1

让我重述一下我认为你的意思。

您有一个长度为 n-1 的位串。如果它的数字是 increase/decrease 的模式，则描述了一组适合该模式的排列。该集合可以按升序排列。

你希望能够解决两个问题。

给出符合模式的排列，说出它在那个顺序中的位置（即 "rank" 它）
给定一个数字，产生顺序中该位置的排列（即 "unrank" 它）

理想情况下，您希望能够解决这些问题，而不必生成符合模式的所有排列。

两者的关键是以下函数：

def count_matching (bitstring, start):
    ''' Returns how many permutations of 1..(len(bitstring) + 1)
    ''' match bitstring with starting value start
    # some implementation here.

这可以很容易地递归计算。但是，以幼稚的方式进行操作会生成所有排列。但是，如果我们向 memoize 添加一个缓存层，那么我们将存储多项式数量的数据并进行多项式调用来填充它。

这是为您的示例缓存后获得的数据：

{
    ('010', 1): 2,
    ('010', 2): 2,
    ('010', 3): 1,
    ('010', 4): 0,
    ('10', 1): 0,
    ('10', 2): 1,
    ('10', 3): 1,
    ('0', 1): 1,
    ('0', 2): 0,
    ('', 1): 1
}

现在这似乎是少量模式的大量数据。但是对于长度 n 的排列，条目的数量像 O(n^2) 一样增长，填充它的调用数量像 O(n^3) 一样增长。（任何眼尖的读者都可能会想出如何及时填充它 O(n^2)。我将使用简单版本。）

有了这个，我们可以根据以下想法进行排名并找出它必须是哪种排列。

假设我们要找到秩为 4 的排列。我们的起始号码列表是 (1 2 3 4)。我们可以跳过 0 个以 ('010', 1) 开头的排列，答案将是 2 个以 ('010', 2).

开头的排列中的第二个

取第二个数字 2，我们的部分排列是 [2，我们有数字 (1 3 4)。我们正在寻找位串 '10' 的第二个。我们跳过以 ('10', 1) 开头的 0 个排列，以 ('10', 2) 开头的 1，并希望以 ('10', 3).

开头的 1 中的第一个排列

取第三个数字 4，我们的部分排列是 [2, 4，我们有数字 (1 3)。和以前一样，我们发现我们想要第一个 ('0', 1).

取第一个数字 1，我们的部分排列是 [2, 4, 1，我们有数字 (3)。选择不多。

所以我们完成并得到[2, 4, 1, 3]。您可以验证的是第 4 个。

所以我们以 [2, 4, 3, 1] 结束。

我们也可以走另一条路。采用相同的排列，我们从 [2, 4, 3, 1] 开始并想要它的排名。

前面有多少第一个数字不同的？它使用了第二个可能的第一个数字。从 ('010', 1) 的条目我们知道有 2 个。剩下的数字是 1 3 4.

它前面第二个数字不同的有多少个？它使用第三个可能的第二个数字。从 ('10', 1) 和 ('10', 2) 的条目我们知道前面还有 1 个。

我们现在还剩下 1 3 个号码。 None 在第三个数字中排在它之前。再一次，none 在最后。

前面有3的一定是4级

好了。为了记忆一个递归函数，您现在可以按等级查找排列，或者直接对给定的排列进行排名。

用 DI 序列排列排列

permutation ranking with DI sequence

arrays

algorithm

combinations

permutation

ranking