DI序列的排列排序 [英] permutation ranking with DI sequence

问题描述

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

I want to rank and unrank through a subset of permutations given by length. The subset is definded as follows:

排列长度4的示例:

我们输入了位串长度3(始终为置换长度-1)

We have the Input the Bitstring length 3 (always permutation length - 1)

010

0表示2个连续元素在增加I.

0 means 2 consecutive elements are Increasing.

1表示2个连续元素在增加D.

1 means 2 consecutive elements are Decreasing.

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

For this Bitstring exist the subset with following permutations: 1324,1423,2314,2413,3412

我要排列和取消排列的排列的位串定义子集?给定的位串有一种算法吗?

The bitstring defined subset of permutations i want to rank and unrank? Is there an algotrithmic way for a given bitstring to do this?

推荐答案

让我重述一下我认为您的意思的问题.

Let me restate the problem that I think you mean.

您有一个长度为n-1的字符串.如果其数字是增加/减少的模式，则说明一组适合该模式的排列.该集合可以按升序排列.

You have a bit string of length n-1. If its digits are a pattern of increase/decrease, that describes a set of permutations that fit the pattern. That set can be put into ascending order.

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

You want to be able to solve two problems.

1. 给出适合模式的排列，说出排列顺序(即排列"它)
2. 给出一个数字，按顺序生成该位置处的排列(即取消排序")

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

And ideally you'd like to be able to solve these without having to generate all of the permutations that fit the pattern.

两者的关键是以下功能:

The key to both is the following function:

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

这可以很容易地递归计算.但是，天真的方法会生成所有排列.但是，如果我们在memoize上添加一个缓存层，那么我们将存储多项式的数据并进行多项式调用以填充它.

This can be calculated recursively fairly easily. However doing it the naive way generates all permutations. But if we add a caching layer to memoize it, then we store a polynomial amount of data and make a polynomial number of calls to fill it in.

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

Here is the data you get once it is cached for your example:

{
    ('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).我要使用简单的版本.)

Now this seems like a lot of data for a small number of patterns. But for a permutation of length n the number of entries grows like O(n^2) and the number of calls to populate it grows like O(n^3). (Any eagle eyed readers may figure out how to populate it in time O(n^2). I'm going with the simple version.)

掌握了这一点，我们可以按照以下思路进行排名，弄清楚它必须是哪个排列.

With this in hand, we can take a rank and figure out which permutation it must be with the following idea.

假设我们要查找第4级排列.我们的数字起始列表是(1 2 3 4).我们可以跳过以('010', 1)开头的0个排列，答案将是用('010', 2) 2个排列中的第二个.

Suppose that we want to find the rank 4 permutation. Our starting list of numbers is (1 2 3 4). We can skip over 0 permutations which start with ('010', 1) and the answer will be the second of the 2 with ('010', 2).

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

Take the second number 2 and our partial permutation is [2, and we have the numbers (1 3 4). We are looking for the 2nd for bitstring '10'. We skip over the 0 permutations which start ('10', 1), the 1 with ('10', 2) and want the first of the 1 with ('10', 3).

取第三个数字4，我们的部分置换为[2, 4，我们有数字(1 3).如前所述，我们希望使用('0', 1)中的第一个.

Take the third number 4 and our partial permutation is [2, 4, and we have the numbers (1 3). As before we find that we want the first of the 1 with ('0', 1).

取第一个数字1，我们的部分置换为[2, 4, 1，我们有数字(3).选择不多.

Take the first number 1 and our partial permutation is [2, 4, 1 and we have the numbers (3). There aren't a lot of choices.

因此，我们完成并获得[2, 4, 1, 3].您可以验证的是第四名.

So we finish and get [2, 4, 1, 3]. Which you can verify is the 4th.

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

我们也可以采用其他方式.采用相同的排列，我们从[2, 4, 3, 1]开始并希望其排名.

We can also go the other way. Taking the same permutation, we start with [2, 4, 3, 1] and want its rank.

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

How many are before it that differ in the first digit? It used the 2nd possible first number. From the entry for ('010', 1) we know there are 2. And the numbers left are 1 3 4.

之前有多少个与第二位数字不同?它使用第三个可能的第二个数字.从('10', 1)和('10', 2)的条目中，我们知道前面还有1个.

How many are before it that differ in the second digit? It uses the 3rd possible second number. From the entries for ('10', 1) and ('10', 2) we know there is 1 more in front of it.

我们现在剩下数字1 3.第三位没有任何数字.再说一次，最后一个都没有.

We now have the numbers 1 3 left. None came before it in the third digit. And again, none in the last.

前面有3个，必须具有4级​​.

With 3 before it, it must have rank 4.

就在那里.为了记住一个递归函数，您现在可以按等级查找排列，或者直接给定排列排列.

And there you have it. For memoizing one recursive function, you now make finding permutations by rank, or ranking a given permutation straightforward.

这篇关于DI序列的排列排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！