从给定的字典排序中寻找置换
我编写了下面的Python代码，以获取一些整数，并返回在排列的字典顺序中具有该级别的置换。虽然这样做有效，但我担心调用pop()和append()的次数可能会减慢速度。这个函数是一个更大的程序的一部分，它将调用FromRank()数百万次，任何小的效率都可能对整个过程产生很大的影响。
注意: Java的相同主题是这里！
输入：
有四个论点：rank、level、ordered和perm。rank是给定的秩。level是置换减去1的不确定位数。因此，如果置换的大小为8位，那么级别最初为7。ordered最初是list(range(size))，并且总是排序。perm跟踪置换，最初是一个空列表。
代码：
def FromRank(rank,level,ordered,perm):
fact = math.factorial(level)
section = rank // fact
if len(ordered) == 1:
perm.extend(ordered)
return perm
elif rank % fact == 0:
ordered.sort()
nxt = ordered.pop(section - 1)
perm.append(nxt)
ordered.sort(reverse = True)
perm.extend(ordered)
return perm
elif rank < fact:
ordered.sort()
first = ordered.pop(0)
perm.append(first)
return FromRank(rank,level - 1,ordered,perm)
else:
ordered.sort()
nxt = ordered.pop(section)
perm.append(nxt)
rank = rank - (rank // fact) * fact
return FromRank(rank,level - 1,ordered,perm)时间复杂度示例：
虽然该函数的目标是在一个级别上工作，但我运行了以下代码，以查看运行时将如何随着要处理的排列数量的增加而增加。而且，虽然这个函数永远不会在大于20的排列上运行，但我包含了一个部分，给出了一个不断增长的排列的运行时。
我运行这个函数是为了了解这个函数对卷的响应情况。
for j in range(2,11):
start_time = timeit.default_timer()
for i in range(1,math.factorial(j)+1):
x = FromRank(i,j-1,list(range(j)),[])))
elapsed_time = timeit.default_timer() - start_time
print("Permutations of size {} took {} seconds."\
.format(j,elapsed_time))得到了以下几次：
Permutations of size 2 took 0.000249750356557 seconds.
Permutations of size 3 took 0.00016293644837 seconds.
Permutations of size 4 took 0.000660726542604 seconds.
Permutations of size 5 took 0.00366414564209 seconds.
Permutations of size 6 took 0.0185743274595 seconds.
Permutations of size 7 took 0.160154982071 seconds.
Permutations of size 8 took 1.48163329891 seconds.
Permutations of size 9 took 15.2436537109 seconds.
Permutations of size 10 took 177.243403105 seconds.然后，我运行了以下命令，以了解该函数将如何对大型排列作出响应：
for size in [10,50,100,500,1000]:
start_time = timeit.default_timer()
x = FromRank(size ** 2, size - 1, list(range(size)), [])
elapsed_time = timeit.default_timer() - start_time
print(elapsed_time)得到了以下几次：
0.000118032702744
0.00074668514128
0.00260142366255
0.110989229516
0.684973282271回答 1
Code Review用户
发布于 2016-06-24 09:20:06
风格
Python有一个名为PEP 8的样式指南，它绝对值得一读，如果您没有充分的理由不这样做的话，它值得一读。例如，在您的示例中，您的函数名不符合PEP8。如果您愿意，您将在网上找到工具，以自动方式检查您的代码是否符合PEP8。
API /函数签名
您的功能签名有点不清楚。这种情况通常发生在应用递归解决方案时。解决这个问题的一个好方法是定义另一个函数，用正确的参数调用复杂的函数，或者使用默认的参数。
如果我对每件事都有正确的理解，那就是从列表中获得第n次表演的意义。这样做的一个简单方法是有一个以rank和lst为参数的函数。
测试
为了保持简单，编写一个简单(即使效率低下)的解决方案是一个很好的选择，它能够看到模式和/或编写测试，以确保您的工作效率更高，而且确实更有效率。
可以这样编写一个非常简单的解决方案：
def from_rank(rank, lst):
sorted_perm = sorted(itertools.permutations(lst))
return sorted_perm[rank]你可以写一些简单的测试，比如：
tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2])
for lst in tests_cases:
for i in range(math.factorial(len(lst))):
a = list(from_rank(i, lst))
b = list(from_rank2(i, lst))
if a != b:
print(i, a, b)另一个更简单的解决方案
您的解决方案涉及数据的递归和突变。这会使事情变得很难理解。一个更简单的想法可以说，从等级，很容易知道哪个元素将是第一个终年。实际上，如果列表中有n元素，那么您就知道存在长度为n-1的(n-1)!置换，因此rank-th置换对于其第一个元素rank / ((n-1)!)-th元素具有。对于一个较小的列表，您可以重复相同的想法，该列表中的其余元素与排名的其余部分相一致。
这可以写成：
def from_rank2(rank, lst):
my_lst = sorted(lst)
ret = []
while my_lst:
fact = math.factorial(len(my_lst) - 1)
idx, rank = divmod(rank, fact)
ret.append(my_lst.pop(idx))
assert rank == 0 # invalid rank - out of range
return ret请注意，这个解决方案似乎不能很好地处理重复元素的列表。您可以轻松地增强测试套件以显示它：
tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2], [2, 2, 3], [1, 2, 5, 4, 3, 2])https://codereview.stackexchange.com/questions/132760
复制相似问题
腾讯云开发者
