我有一个列表的一些排列组合。
>>> 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.orgwikiFactorial_number_system(因子数系统)
脱口而出，我想出了下面的方法，没有彻底测试。
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)
我想这是一个挑战，所以这是我的（递归）答案。
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
你需要写一个自己的函数 像这样的东西就可以了
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)
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 我们先 "固定 "0，然后把剩下的数进行换元，再固定1，把剩下的数进行换元，以此类推。一旦我们固定了一个数，剩下的数又是换元，所以我们再次从剩下的数中每次固定一个数，然后将剩下的数换元。这样下去，直到我们只剩下一个数字。每一级的定数都有一个相应的 (n-i)! 的组合。
所以这段代码找到了每一级排列组合的 "偏移量"。这个 offset 当我们固定给定组合的数量时，对应于给定组合开始的位置。perm 顺序。对于给定的例子 (0, 2, 3, 1)，我们先看一下给定的 perm 为0，并计算出偏移量为0，然后这就到了 gones 列表（我们将看到它的用法）。然后，在下一级的换位中，我们看到2是定数。为了计算这个的偏移量，我们需要这个2在其余三个数中的 "顺序"。这就是 gones 来发挥作用；如果一个已经固定并被认为的数字（在这种情况下是0）小于当前的固定器，我们减去1来找到新的顺序。然后计算偏移量，并累计。对于下一个数字3，新的顺序是 3 - (1 + 1) = 1 因为之前的固定数0和2都在3的 "左边"。
这种情况一直持续到给定的最后一个数字。perm 既然没有必要看，反正已经确定了。