获取排列计数

Question

我搜索一种算法，它可以为我提供1....n元素的排列计数。如果我定义周期长度。

例如n := 4

<Set of cycle lengths>->permutation count

1,1,1,1->1读取 4 个长度为 1 的周期导致 1 个排列：1,2,3,4

1,1,2->5读取长度为 1 的 2 个周期和长度为 2 的 1 个周期导致 5 种排列：1,2,4,3、1,4,3,2、1,3,2,4、2,1,3,4、3,2,1,4、

2,2->3读取 2 个长度为 2 的周期导致 3 种排列：2,1,4,3、3,4,1,2、4,3,2,1

1,3->9

读取长度为 1 的 1 个周期和长度为3 的 1 个周期导致 9 种排列1,3,2,4、1,3,4,2、1,4,2,3、2,3,1,4、2,4,3,1、3,1,2,4、3,2,4,1、4,1,3,2、4,2,1,3、

4->6读取长度为 4 的 1 个周期会导致 6 种排列：2,3,4,1、2,4,1,3、3,1,4,2、3,4,2,1、4,1,2,3、4,3,1,2

如何计算由周期长度组成的给定集合的排列计数？遍历所有排列不是一种选择。

Answer 1

对于给定的循环类型，我们可以通过写下列表1, ..., n排列，然后根据循环类型的长度适当地将其括起来，从而生成具有该循环类型的排列，以获得用循环符号编写的排列。

例如，如果我们想要循环类型(3, 2, 2)，则排列1, 2, 3, 4, 5, 6, 7括起来为(1 2 3)(4 5)(6 7)，而5, 1, 6, 2, 4, 3, 7给出(5 1 6)(2 4)(3 7)。

很明显，我们以这种方式获得循环类型的所有排列(3, 2, 2)但也很明显，我们可以通过多种不同的方式获得每个排列。高计有两个原因：首先，我们可以对任何周期进行周期性转换：(5 1 6)(2 4)(3 7)与(1 6 5)(2 4)(3 7)或(6 5 1)(2 4)(3 7)排列相同。其次，相同长度的循环可以任意排列：(5 1 6)(2 4)(3 7)与(5 1 6)(3 7)(2 4)排列相同。稍微思考一下应该会说服您，这些是多计的唯一可能原因。

为了解释高计的两个原因，我们将排列总数除以(a(周期长度的乘积，以及(b(任何给定周期长度的周期数的阶乘。在(3, 2, 2)的情况下：我们除以3 × 2 × 2表示 (a(，2!除以 (b(，因为有两个长度为 2 的循环。

由于这是Stack Overflow，这里有一些Python代码：

from collections import Counter
from math import factorial
def count_cycle_type(p):
"""Number of permutations with a given cycle type."""
count = factorial(sum(p))
for cycle_length, ncycles in Counter(p).items():
count //= cycle_length ** ncycles * factorial(ncycles)
return count

例：

>>> count_cycle_type((2, 2))
3
>>> count_cycle_type((3, 2, 2))
210

为了仔细检查正确性，我们可以添加给定长度的所有周期类型的计数n，并检查我们是否得到n!。循环类型是n的分区。我们可以通过递归算法相当简单地计算这些。下面是一些代码来执行此操作。partitions是我们想要的功能;bounded_partitions是一个帮手。

def bounded_partitions(n, k):
"""Generate partitions of n with largest element <= k."""
if k == 0:
if n == 0:
yield ()
else:
if n >= k:
for c in bounded_partitions(n - k, k):
yield (k,) + c
yield from bounded_partitions(n, k - 1)

def partitions(n):
"""Generate partitions of n."""
return bounded_partitions(n, n)

例：

>>> for partition in partitions(5): print(partition)
... 
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)

这是双重检查：所有循环类型的总和计数，总长度5，6，7和20。我们得到5!、6!、7!和20!的预期结果。

>>> sum(count_cycle_type(p) for p in partitions(5))
120
>>> sum(count_cycle_type(p) for p in partitions(6))
720
>>> sum(count_cycle_type(p) for p in partitions(7))
5040
>>> sum(count_cycle_type(p) for p in partitions(20))
2432902008176640000
>>> factorial(20)
2432902008176640000

Answer 2

这可以分解为：

1. 将元素分区到存储桶的方法数量，与每个不同周期大小所需的元素计数相匹配;
2. 对于每个不同的循环大小，乘以将元素均匀划分为所需循环数的独特方法的数量;
乘以
3. 每个循环的不同循环排序的数量

1：对于铲斗尺寸_{s 1}...s k，这适用于 n！/(s₁！ * ... * s_k！(

2：对于包含 m 个元素的存储桶，必须划分为 c 个循环，有 m！/( (m/c(！c * c！( 方式

3：对于包含m个元素的循环，有(m-1(！ 如果 m> 1，则为不同的循环排序，否则只有 1 个排序