查找给定数组的排列的(词典)索引.

Question

给定一个数组说"bca",我需要找到排列数量大于给定排列的排列数.

因此,在该示例中,cab,cba是更大的排列.因此答案是2.

我尝试通过查找数组的词典排名来解决问题,但我无法为说法设计一个有效的算法.

任何帮助/指针在正确的方向是值得赞赏的!

Answer 1

让我们来看看排列dacb.4这里的字典顺序在哪里出现!= 24的排列abcd？

• 考虑第一个字母d.剩下的字母(acb)中有三个小于3的字母d!= 6个排列从每个排列开始,总共18个排列.
• 考虑前两个字母da.在剩余的字母(cb)中,没有小于的字母a(如果有的话,那么将有2个!= 2个排列以d加号开始),总共0个排列.
• 考虑前三个字母dac.在其余的字母(b)中,有一个字母小于1 c,而1!= 1个排列,从dab总共1个排列开始.

所以总共有19个小于的排列dacb.我们来检查一下.

>>> 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中的一个实现:

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

Answer 2

根据阶乘数系统和Lehmer代码,有一种非常简洁的方法.我们的想法是为每个可能的排列分配一个数字代码,该排列对编码值的出现顺序(Lehmer代码)进行编码.然后,您可以将Lehmer代码转换为一个数字,该数字确定所有排列列表中的排列索引(这使用阶乘数系统).给定置换的索引,然后可以计算(n! - 1)并减去索引以确定有多少排列.

如果你很好奇如何做到这一点,我有一个这种算法的实现,它允许你从排列映射到索引,反之亦然.我还谈到了如何做到这一点 ; 细节在幻灯片的后半部分.

希望这可以帮助!