我要寻找给定一组数字的算法（例如1 2 3）和索引（例如2）将让我按照字典顺序这些数字的第二置换。例如，在这种情况下，算法将返回1 3 2

I am looking for an algorithm that given a set of numbers (for example 1 2 3) and an index (for example 2) will get me the second permutation of those numbers according to a lexicographic order. For example in this case the algorithm will return 1 3 2.

推荐答案

下面是一个简单的解决办法：

Here is a simple solution:

from math import factorial # python math 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
    f = factorial(n - k)  # compute factorial once per iteration
    d = i // f            # use integer division (like division + floor)
    print(p[d]),          # print permuted number with trailing space
    p.remove(p[d])        # delete p[d] from p
    i = i % f             # reduce i to its remainder

输出：

3 2 1

时间复杂度为的 0 的（N ^ 2）如果 P 是一个列表，而 0 的（N ）摊销如果 P 是一个哈希表，因子是precomputed。

The time complexity is O(n^2) if p is a list, and O(n) amortized if p is a hash table and factorial is precomputed.