排列与DI序列分级(permutation ranking with DI sequence)

我想排名，并通过长排列给出的一个子集unrank。该子集的肺癌如下：

例如用于置换长度4：

我们输入的比特串长度为3（总置换长度 - 1）

010

0表示连续的2个元素是I D.加强。

1意味着连续的2个元素是D ecreasing。

对于这个位串存在与下面排列的子集： 1324 ， 1423 ， 2314 ， 2413 ， 3412

位串排列我想排名和unrank定义的子集？是否有一个给定的位串的algotrithmic方式做到这一点？

让我重申，我想你所指的问题。

你有长度的比特串n-1 如果它的数字是增加/减少的格局，即描述了一组适合的图案排列。这组可投入升序排列。

你想成为能够解决两个问题。

鉴于适合的图案排列，说那里是按照这个顺序（即“等级”的话）
给定一个数，产生是在为了那个地方的置换（即“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' 。我们跳过在0置换其启动('10', 1)将1 ('10', 2)并希望在第一1与('10', 3)

从第三个号码4和我们的局部排列是[2, 4 ，我们有数字(1 3) 正如之前我们发现，我们要与第1的('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左右。在第三位前无来了。再次，没有在最后。