我试图找到一个有效的算法来寻找一个多集的排列,给定一个索引。在
例如:给定{1, 3, 3}
。所有按字典序升序排列的排列都是{133, 313, 331}
。这些元素被索引为{0, 1, 2}
。给定index=2
,结果是331。在
I found an algorithm查找给定词典索引的集合的置换。他的算法是有效的:O(n^2)。在
但是,该算法是在一个适当的集合上测试的(例如{1, 2, 3}
),而在我的测试中并不正确。我在这里描述他的python代码,这样您就可以很容易地理解了。在
from math import factorial, floor #// python library
from math import factorial, floor #// python library
i=5 #// i is the lexicographic index (counting starts from 0)
n=3 #// n is the length of the permutation
p = range(1,n+1) #// p is a list from 1 to n
for k in range(1,n+1): #// k goes from 1 to n
d = i//factorial(n-k) #// use integer division (like division+floor)
print(p[d]),
p.remove(p[d]) #//delete p[d] from p
i = i % factorial(n-k) #// reduce i to its remainder
似乎像预期的那样有效
^{pr2}$时间复杂性:
O(n^2)
。在相关问题 更多 >
编程相关推荐