查找给定数组的排列的(字典序)索引. [英] Finding the (lexicographic) index of a permutation of a given array.

问题描述

给定一个数组bca"，我需要找到字典序数大于给定排列的排列数.

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

因此，在此示例中，cab、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.

感谢任何正确方向的帮助/指示！

Any help/pointers in the right direction is appreciated!

推荐答案

我们来看看置换dacb.这在 4 个中按字典顺序排列在哪里！= abcd 的 24 个排列?

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 个排列.
• 考虑前两个字母 da.在剩余的字母 (cb) 中，没有小于 a 的字母(如果有的话，将有 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 的排列.

Looks good. So there are 4! − 19 − 1 = 4 permutations that are greater than 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屋！