按索引号获取指定度数的排列

Question

我已经工作了几个小时,但无法弄明白.

将排列度定义为创建它时需要组合的最小转置数.所以程度(0, 1, 2, 3)为0,程度(0, 1, 3, 2)为1,程度(1, 0, 3, 2)为2,等等.

将空间Snd看作n具有度数的长度序列的所有排列的空间d.

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

我希望这样实现O(sane); 这意味着如果你要求排列数17,算法不应该遍历0到16之间的所有排列来检索你的排列.

不知道怎么解决这个问题？

(如果你要包含代码,我更喜欢Python,谢谢.)

更新:

我想要一个解决方案

1. 排列是根据它们的词典顺序排序的(而不是通过手动排序它们,而是通过一个有效的算法来给它们开始的词典顺序)和
2. 我希望算法也接受不同程度的序列,所以我可以说"我希望在范围(5)的置换空间中的所有1或3或4级排列中排列数为78".(基本上函数会取一个度数元组.)这也会影响从排列计算索引的反函数; 根据度数集,指数会有所不同.

我过去两天试过解决这个问题而且我没有成功.如果你能提供Python代码,那就是最好的.

Answer 1

这个答案不如我的另一个答案优雅/高效，但它描述了一种多项式时间算法，可以应对排列顺序的额外约束。我将描述一个子例程，给定一个 n 元素排列的前缀和一组度数，计算有多少个排列具有该前缀和属于该集合的度数。给定这个子例程，我们可以对指定子集中指定排名的排列进行 n 元搜索，一次扩展已知前缀一个元素。

我们可以将 n 元素排列 p 可视化为 n 顶点、n 弧有向图，其中对于每个顶点 v，都有一条从 v 到 p(v) 的弧。该有向图由顶点不相交循环的集合组成。例如，排列 31024 看起来像

 _______
/       \
\->2->0->3
 __     __
/  |   /  |
1<-/   4<-/ .

给定排列的前缀，我们可以可视化与该前缀对应的子图，它将是顶点不相交路径和循环的集合。例如，前缀 310 看起来像

2->0->3
 __
/  |
1<-/ .

我将描述（1）此前缀的扩展（即排列）和（2）相关元素集上的完整排列之间的双射。此双射最多可保留循环数（即元素数减去次数）的常数项。常数项是前缀中的循环数。

(2) 中提到的排列位于以下元素集上。从原始集合开始，删除前缀中完整的循环所涉及的所有元素，并为每个路径引入一个新元素。例如，如果前缀是310，那么我们删除完整的循环1，并为路径2->0->3引入一个新元素A，得到集合{4，A}。现在，给定集合（1）中的排列，我们通过删除已知循环并用新元素替换每个路径来获得集合（2）中的排列。例如，排列31024对应于排列4->4、A->A，排列31042对应于排列4->A、A->4。我声称（1）该映射是双射，并且（2）它保留了之前描述的度数。

第一类第 (n,k) 个斯特林数的定义或多或少，写为

[n]
[ ]
[k]

（ASCII 艺术方括号）是 n - k 次的 n 元素排列的数量。要计算 n 元素排列的 r 元素前缀的扩展数，请计算 c，即前缀中的完整循环数。总和，对于指定集合中的每个度数 d，斯特林数

[  n - r  ]
[         ]
[n - d - c]

第一类，将“不可能”指数的项视为零（斯特林数的一些出于分析动机的定义在意想不到的地方是非零的）。

为了从排列中获得排名，我们再次进行 n 元搜索，只不过这次我们使用排列而不是排名来指导搜索。

下面是两者的一些 Python 代码（包括测试函数）。

import itertools

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    ans = memostirling1.get((n, k))
    if ans is None:
        if not 1 <= k <= n: return 0
        ans = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
        memostirling1[(n, k)] = ans
    return ans

def cyclecount(prefix):
    c = 0
    visited = [False] * len(prefix)
    for (i, j) in enumerate(prefix):
        while j < len(prefix) and not visited[j]:
            visited[j] = True
            if j == i:
                c += 1
                break
            j = prefix[j]
    return c

def extcount(n, dset, prefix):
    c = cyclecount(prefix)
    return sum(stirling1(n - len(prefix), n - d - c) for d in dset)

def unrank(n, dset, rnk):
    assert rnk >= 0
    choices = set(range(n))
    prefix = []
    while choices:
        for i in sorted(choices):
            prefix.append(i)
            count = extcount(n, dset, prefix)
            if rnk < count:
                choices.remove(i)
                break
            del prefix[-1]
            rnk -= count
        else:
            assert False
    return tuple(prefix)

def rank(n, dset, perm):
    assert n == len(perm)
    rnk = 0
    prefix = []
    choices = set(range(n))
    for j in perm:
        choices.remove(j)
        for i in sorted(choices):
            if i < j:
                prefix.append(i)
                rnk += extcount(n, dset, prefix)
                del prefix[-1]
        prefix.append(j)
    return rnk

def degree(perm):
    return len(perm) - cyclecount(perm)

def test(n, dset):
    for (rnk, perm) in enumerate(perm for perm in itertools.permutations(range(n)) if degree(perm) in dset):
        assert unrank(n, dset, rnk) == perm
        assert rank(n, dset, perm) == rnk

test(7, {2, 3, 5})