0

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

排列长度 4 的示例：

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

010

0表示 2 个连续的元素正在I增加。

1表示 2 个连续的元素正在D减少。

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

我想要排名和取消排名的位串定义的排列子集？给定的位串是否有一种算法方法可以做到这一点？

4

1 回答 1

1

让我重申我认为你的意思的问题。

你有一个长度的字符串n-1。如果它的数字是增加/减少的模式，则描述了一组适合该模式的排列。该集合可以按升序排列。

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

  1. 给定一个符合模式的排列，说出它在那个顺序中的位置（即“排列”它）
  2. 给定一个数字，产生在该位置的排列顺序（即“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)。我们正在寻找第二个 bitstring '10'。我们跳过以 开头的 0 排列，以 1 开头('10', 1)的 1('10', 2)并希望以 1 开头的第一个排列('10', 3)。

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

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

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

所以我们以[2, 4, 3, 1].

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

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

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

我们现在1 3剩下的数字。第三位数字没有出现在它之前。再一次，最后没有。

前面有 3，它必须有 4 级。

你有它。为了记忆一个递归函数，您现在可以通过等级查找排列，或直接对给定排列进行排序。

于 2019-06-12T00:11:44.550 回答