python - 通过索引号获取指定次数的排列

Question

我已经为此工作了几个小时，但无法弄清楚。

将排列的次数定义为创建它所需组合的最小换位数。所以 (0, 1, 2, 3) 的度数为 0，(0, 1, 3, 2) 的度数为 1，(1, 0, 3, 2) 为 2 等

将空间 Snd 视为长度为 n 且度数为 d 的所有排列的空间。

我想要两种算法。一个在该空间中进行排列并为其分配一个索引号，另一个在 Snd 中获取项目的索引号并检索其排列。索引号显然应该是连续的(即在 0 到 len(Snd)-1 范围内，每个排列都有一个不同的索引号。)

我希望在 O(sane) 中实现它；这意味着如果您要求排列编号 17，则算法不应遍历 0 到 16 之间的所有排列来检索您的排列。

知道如何解决这个问题吗？

(如果您要包含代码，我更喜欢 Python，谢谢。)

更新:

我想要一个解决方案

1. 排列是根据它们的字典顺序排序的(不是通过手动排序，而是通过一种有效的算法，让它们以字典顺序开始)和
2. 我希望算法也接受不同度数的序列，所以我可以说“我想要范围 (5) 排列空间中所有 1、3 或 4 度排列中的排列数 78”。 (基本上这个函数需要一个度元组。)这也会影响从排列计算索引的反向函数；根据学位集，索引会有所不同。

过去两天我尝试解决这个问题，但没有成功。如果您能提供 Python 代码，那就最好了。

Answer 1

长度 n 和次数 d 的排列正是那些可以写成 k = n - d 循环的组合，它们划分了 n 个元素。这种排列的数量由 Stirling numbers of the first kind 给出。 , 在方括号中写在 k 之上 n。

第一类斯特林数满足递推关系

[n]           [n - 1]   [n - 1]
[ ] = (n - 1) [     ] + [     ]
[k]           [  k  ]   [k - 1],

表示，直观上，将n个元素划分为k圈的方式数，就是将n-1个非极大值元素划分为k圈，并以n-1种方式之一拼接在最大元素上，或者将最大元素在自己的循环中，并将 n - 1 个非最大元素划分为 k - 1 个循环。使用重复值表，可以跟踪决策。

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    if (n, k) not in memostirling1:
        if not (1 <= k <= n): return 0
        memostirling1[(n, k)] = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
    return memostirling1[(n, k)]

def unrank(n, d, i):
    k = n - d
    assert 0 <= i <= stirling1(n, k)
    if d == 0:
        return list(range(n))
    threshold = stirling1(n - 1, k - 1)
    if i < threshold:
        perm = unrank(n - 1, d, i)
        perm.append(n - 1)
    else:
        (q, r) = divmod(i - threshold, stirling1(n - 1, k))
        perm = unrank(n - 1, d - 1, r)
        perm.append(perm[q])
        perm[q] = n - 1
    return perm