@Shalashanka

Как вычислить количество расположений чисел в строке, которые можно получить из начальной строки любой последовательностью перестановок?

Я не могу понять как это можно сделать математически
  • Вопрос задан
  • 74 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
(Полное условие есть в комментариях к вопросу)

Алгоритмически тут такое решение: Постройте граф из n вершин, где есть ребро между всеми парами вершин, которые можно менять местами. Подсчитайте размеры компонент связности и перемножте их факториалы. Так, если компонента всего одна, то ответ будет n! (все возможные перестановки из n чисел можно получить так).

Это работает потому, что в каждой компоненте можно получить любую перестановку. Доказательство: строим остовное дерево в компоненте. Потом берем любой лист и перетаскиваем туда любое число по ребрам остовного дерева. Отрезаем лист от дерева. Повторяем эту операцию пока не останется только одна вершина.

Если нужно именно математическая формула от P, то тут все сложно, осбоенно, когда числа P достаточно большие. Например, M=6, P1=3 P2=4. Из вершин 3 и 4 вообще нет ребер, а ребро P2 есть только между крайними вершинам. Подобным образом можно создать весьма сложные структуры.

Однако, если все P меньше равны половины N, то есть простой ответ. В графе будет GCD(P1+1,...,PM+1) компонент связности - все вершины, дающие один и тот же остаток от деления на наибольший общий делитель P+1. И ответ будет что-то вроде (floor(N/G)!)^G*(floor(N/G)+1)^(N%G) (где G - этот самый наибольший общий делитель всех P, увеличенных на 1).

Это потому, что при достаточно маленьких P, всегда можно отложить их в одну или другую сторону и так в итоге сделать шаг длинной G.

Доказательство примерно такое: Рассмотрим первую половину вершин. Из них можно отложить вправо самое большое P. А потом влево любое из оставшихся P. Так мы фактически отложили от всех этих вершин любую разность двух P вправо. Если сначала отложить вправо меньшее P, а потом максимальное P назад, то мы отложили ту же разность влево. Из соображений симметричности получается, что мы можем отложить любую разность P от всех вершин в любую сторону. Все разности также меньше половины N. Продолжая этот процесс, как в алгоритме эвклида, мы получим, что можно от каждой вершины отложить G, а значит все вершины с одинаковым остатоком от деления на G принадлежат одной и той же компоненте связности.

Если какие-то P больше половины (аккуратно сами посмотрите, там +-1 где-то возможно нужно), то я не знаю формулу. Остается только писать DFS на графе.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы