在给定索引的情况下,我试图找到一种有效的算法来查找多集的排列.
例如:给定{1, 3, 3}.按升序词典顺序排列的所有排列都是{133, 313, 331}.这些元素被索引为{0, 1, 2}.鉴于index=2,结果是331.
我找到了一种算法来查找给定词典索引的集合的排列.他的算法很有效: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 …我试图找到一种最有效的方法来找到一组'0'和'1'给定索引的排列.
例如:给定l = [0,0,1,1].以升序排列的所有排列是{0011,0101,0110,1001,11010,1100}.这些元素从0 - > 5索引.给定index = 2,结果为0110.
我在这里找到了输入整数多重集的算法(例如l = [1,2,2]).他的算法是有效的(O(N ^ 2)).但是,我的multiset只包含'0'和'1',需要O(N)或更少.N是列表的长度
能帮助我吗？请注意,我的实际测试很大(len(l)是1024),因此intertool库不适合.我试图尽可能加快它(例如,使用gmpy2 ......)
基于1,以下是我的尝试,但它是O(N ^ 2)
from collections import Counter
from math import factorial
import gmpy2
def permutation(l, index):
if not index:
return l
counter = Counter(l)
total_count = gmpy2.comb(len(l), counter['1'])
acc = 0
for i, v in enumerate(l):
if i > 0 and v == l[i-1]:
continue
count = total_count * counter[v] / len(l)
if acc + count > index:
return [l[i]] …