获取排列计数

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 读取 2 个长度为 1 的循环和 1 个长度为 2 的循环导致 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 的循环和 1 个长度为 3 的循环导致 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 读取 1 个长度为 4 的循环导致 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：对于存储桶大小 s₁...s_k，计算结果为 n!/(s₁!* ... * s_k!)

2：对于一个包含m个元素的桶，必须划分成c个循环，有m!/( (m/c)!^c * c!)方式

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

Answer 2

对于给定的循环类型，我们可以通过写下列表 1, ..., n 的排列，然后根据循环类型的长度将其适当地括起来，来生成该循环类型的排列，得到cycle notation.

中的排列

例如，如果我们想要循环类型 (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) 的情况下：我们对 (a) 除以 3 × 2 × 2，对 (b) 除以 2!，因为有两个长度为 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。我们可以通过递归算法相当简单地计算这些。这是一些代码来做到这一点。 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

获取排列计数

Get permutation count

algorithm

math

permutation

combinatorics

circular-permutations