找到一个给定数组的排列的（字典）指数。 [英] Finding the (lexicographic) index of a permutation of a given array.

问题描述

鉴于阵列说BCA，我需要找到置换它们lexicographicaly比给定的排列更大的数量。

Given an array say "bca", I need to find the number of permutations which are lexicographicaly greater than the given permutation.

因此​​，在此实例中，驾驶室，CBA是置换这是更大的。因此，答案是2。

Thus, in this example, cab, cba are permutations which are greater. Thus the answer would be 2.

我试图找到阵列的字典排名接近的问题，但我不能够设计出一个高效的算法为说。

I tried approaching the problem by finding the lexicographic ranking of the array, but am not able to devise an efficient algorithm for the say.

任何帮助/方向是正确的指针是AP preciated！

Any help/pointers in the right direction is appreciated!

推荐答案

让我们来看看置换 DACB 。哪里该进来的字典顺序中4！ =的 24排列ABCD ？

Let's look at the permutation dacb. Where does this come in lexicographic order among the 4! = 24 permutations of abcd?

• 在考虑的第一个字母 D 。在余下的字母（ ACB ）有三个字母比 D ，和3个更小的！ = 6置换开始与他们中的每一个，总共18个置换。
• 在考虑前两个字母大。在余下的字母（ CB ）有没有字母比小的（如果有任何将有2！ = 2的排列开始 D 加上各一个），共计0排列。
• 在考虑前三个字母 DAC 。在余下的字母（ B ）有一个字母比 c越小和1！ = 1排列开始 DAB ，共计1置换。

• Consider the first letter d. Among the remaining letters (acb) there are three letters smaller than d, and 3! = 6 permutations starting with each one of them, for a total of 18 permutations.
• Consider the first two letters da. Among the remaining letters (cb) there are no letters smaller than a (if there were any there would be 2! = 2 permutations starting with d plus each one), for a total of 0 permutations.
• Consider the first three letters dac. Among the remaining letters (b) there is one letter smaller than c, and 1! = 1 permutations starting with dab, for a total of 1 permutation.

因此​​，总共有19排列比 DACB 小。让我们来看看这一点。

So in total there are 19 permutations smaller than dacb. Let's check that.

>>> from itertools import permutations
>>> list(enumerate(''.join(p) for p in permutations('abcd')))
[(0, 'abcd'), (1, 'abdc'), (2, 'acbd'), (3, 'acdb'),
 (4, 'adbc'), (5, 'adcb'), (6, 'bacd'), (7, 'badc'),
 (8, 'bcad'), (9, 'bcda'), (10, 'bdac'), (11, 'bdca'),
 (12, 'cabd'), (13, 'cadb'), (14, 'cbad'), (15, 'cbda'),
 (16, 'cdab'), (17, 'cdba'), (18, 'dabc'), (19, 'dacb'),
 (20, 'dbac'), (21, 'dbca'), (22, 'dcab'), (23, 'dcba')]

看起来不错。因此，有4！ - 19 - 1 = 4的排列，比 DACB 大于

现在应该清楚如何推广，使算法的方法。下面是用Python实现：

It should be clear now how to generalize the method to make an algorithm. Here's an implementation in Python:

from math import factorial

def lexicographic_index(p):
    """
    Return the lexicographic index of the permutation `p` among all
    permutations of its elements. `p` must be a sequence and all elements
    of `p` must be distinct.

    >>> lexicographic_index('dacb')
    19
    >>> from itertools import permutations
    >>> all(lexicographic_index(p) == i
    ...     for i, p in enumerate(permutations('abcde')))
    True
    """
    result = 0
    for j in range(len(p)):
        k = sum(1 for i in p[j + 1:] if i < p[j])
        result += k * factorial(len(p) - j - 1)
    return result

def lexicographic_followers(p):
    """
    Return the number of permutations of `p` that are greater than `p`
    in lexicographic order. `p` must be a sequence and all elements
    of `p` must be distinct.
    """
    return factorial(len(p)) - lexicographic_index(p) - 1

这篇关于找到一个给定数组的排列的（字典）指数。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！