Получить счетчик перестановок

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, ..., 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), но также ясно, что мы можем получить каждую перестановку несколькими различными способами. Существует две причины перерасчета: во-первых, мы можем сделать циклический c сдвиг для любого из циклов: (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). Немного размышлений должно убедить вас, что это единственно возможные причины перерасчета.

Чтобы учесть обе причины перерасчета, мы разделим общее количество перестановок на (а) произведение длин цикла, и также (b) факториал количества циклов для любой заданной длины цикла. В случае (3, 2, 2): мы делим на 3 × 2 × 2 для (a) и 2! для (b), потому что есть два цикла длины 2.

Поскольку это переполнение стека, вот некоторые 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. , умноженное на количество циклов c порядков