Python，置换为置换指数函数

Question

我有一个列表的一些排列：

>>> import itertools
>>> perms = list(itertools.permutations([0,1,2,3]))
>>> perms
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> len(perms)
24

我可以使用什么函数（无需访问列表 perm）来获取任意排列的索引，例如(0, 2, 3, 1) -> 3?

（您可以假设置换元素总是从零开始的升序整数列表。）

提示：可能涉及阶乘数制。 https://en.wikipedia.org/wiki/Factorial_number_system

Answer 1

我想这是一个挑战，所以这是我的（递归）答案：

import math
import itertools

def get_index(l):
    # In a real function, there should be more tests to validate that the input is valid, e.g. len(l)>0
    # Terminal case
    if len(l)==1:
        return 0

    # Number of possible permutations starting with l[0]
    span = math.factorial(len(l)-1)

    # Slightly modifying l[1:] to use the function recursively
    new_l = [ val if val < l[0] else val-1 for val in l[1:] ]

    # Actual solution
    return get_index(new_l) + span*l[0]


get_index((0,1,2,3))
# 0
get_index((0,2,3,1))
# 3
get_index((3,2,1,0))
# 23
get_index((4,2,0,1,5,3))
# 529
list(itertools.permutations((0,1,2,3,4,5))).index((4,2,0,1,5,3))
# 529

Answer 2

我突然想到了以下内容，没有彻底测试它。

from math import factorial
elements = list(range(4))
permutation = (3, 2, 1, 0)
index = 0
nf = factorial(len(elements))

for n in permutation:
    nf //= len(elements)
    index += elements.index(n) * nf
    elements.remove(n)

print(index)

编辑： 将 nf /= len(elements) 替换为 nf //= len(elements)

Answer 3

您需要编写自己的函数。这样的东西会起作用

import math

def perm_loc(P):

    N = len(P)
    assert set(P) == set(range(N))

    def rec(perm):
        nums = set(perm)
        if not perm:
            return 0
        else:
            sub_res = rec(perm[1:])                  # Result for tail of permutation
            sub_size = math.factorial(len(nums) - 1) # How many tail permutations exist
            sub_index = sorted(nums).index(perm[0])  # Location of first element in permutaiotn
                                                     # in the sorted list of number
            return sub_index * sub_size + sub_res

    return rec(P)

完成所有工作的函数是 rec，perm_loc 只是作为它的包装器。请注意，此算法基于 itertools.permutation 碰巧使用的置换算法的性质。

下面的代码测试了上面的功能。首先是你的样本，然后是 range(7):

的所有排列

print perm_loc([0,2,3,1]) # Print the result from the example

import itertools

def test(N):
    correct = 0
    perms = list(itertools.permutations(range(N)))
    for (i, p) in enumerate(perms):
        pl = perm_loc(p)
        if i == pl:
            correct += 1
        else:
            print ":: Incorrect", p, perms.index(p), perm_loc(N, p)
    print ":: Found %d correct results" % correct

test(7) # Test on all permutations of range(7)

Answer 4

from math import factorial

def perm_to_permidx(perm):
    # Extract info
    n = len(perm)
    elements = range(n)
    # "Gone"s will be the elements of the given perm
    gones = []
    # According to each number in perm, we add the repsective offsets
    offset = 0
    for i, num in enumerate(perm[:-1], start=1):
        idx = num - sum(num > gone for gone in gones)
        offset += idx * factorial(n - i)
        gones.append(num)
    return offset

the_perm = (0, 2, 3, 1)
print(perm_to_permidx(the_perm))
# 3

解释：给定范围内的所有排列都可以看作一组排列。因此，例如，对于 0, 1, 2, 3 的排列，我们首先 "fix" 0 并排列其余部分，然后固定 1 并排列其余部分，依此类推。一旦我们确定了一个数字，剩下的就是排列；所以我们再次从剩余的数字中一次固定一个数字并排列其余的数字。这种情况一直持续到我们只剩下一个数字。每个固定级别都有相应的 (n-i)! 排列。

所以此代码为每个排列级别找到 "offsets"。当我们按顺序固定 perm 的数字时，offset 对应于给定排列的开始位置。对于给定的 (0, 2, 3, 1) 示例，我们首先查看给定 perm 中的第一个数字，即 0，并将偏移量计算为 0。然后进入 gones 列表（我们将见其用法）。然后，在下一级排列中，我们将 2 视为固定数。为了计算这个的偏移量，我们需要剩余三个数字中这个 2 的 "order"。这就是 gones 发挥作用的地方；如果一个已经固定和考虑的数字（在本例中为 0）小于当前固定器，我们减去 1 以找到新顺序。然后计算并累加偏移量。对于下一个数字 3，新顺序是 3 - (1 + 1) = 1，因为之前的固定器 0 和 2 都在 3 的 "left"。

这一直持续到给定 perm 的最后一个数字，因为不需要查看它；反正已经确定了。

Python，置换为置换指数函数

Python, permutation to permuation-index function

python

permutation

factorial

itertools