Алгоритм ранга перестановки

Question

Я изо всех сил пытаюсь найти эффективный алгоритм для вычисления ранга перестановки, и наоборот (перестановка для данного ранга).Может кто-нибудь дать несколько указателей?

Answer 1

У вас есть повторяющиеся элементы в массиве?

Если имеются только уникальные элементы , следующая рекурсия вычисляет ранг X[m:n] как перестановку длины n-m+1:

Ранг (X, m: n) = RankOfElement (X [m], X [m: n]) * Факториал (n - m) + Ранг (X, (m + 1): n)

И Rank, и RankOfElement начинаются с нуля (начиная с 0).

В основном, Rank(permutation) = Rank(first permutation starting with first letter of permutation) + Rank(permutation with first letter deleted), например для строки EDCBA это означает Rank(EDCBA) = Rank(EABCD) + Rank(DCBA).

Это можно расширить до неуникальных случаев, изменив первый термин:

Ранг (X, m: n) = Ранг (X, (m + 1): n) + ∑ более (y ∈ X [m: n], y

Answer 2

РЕДАКТИРОВАТЬ

Я только что видел ваш комментарий.Хорошая графика!Право, что вы хотите, это обход дерева.

Обратите внимание, как каждая позиция в вашей перестановке имеет отдельный уровень в дереве?Каждый путь от корневого узла до конечного узла в этом дереве является возможной перестановкой.

Таким образом, это означает, что ваш ранг обладает некоторой гибкостью.Вы должны определить это.Просто сделайте любой тип обхода по дереву, который вы хотите (inorder, preorder, postorder, DFS, BFS), чтобы дать вам нумерацию листовых узлов, увеличенных по мере прохождения прямо через каждый листовой узел.

Так что просто выберите обход и ранжирование ваших перестановок, которые будут наиболее естественными или удобными для вашего приложения.Если вы не можете выбрать, спросите / dev / random, какой обход вы должны использовать.

КОНЕЦ РЕДАКТИРОВАНИЯ

Ну, во-первых, это нужно рассматривать как базовое преобразование,Каждая перестановка находится в точке (это ранг).Подумайте о двоичном.Какой эффективный алгоритм для вычисления перестановки из 2 алфавитов для n символов?Просто назначьте ранг, и вы получите перестановку.

То же самое работает для алфавитов другого размера.Очевидно, что все будет сложнее, если ваши позиции имеют алфавиты разного размера, но вы все равно можете использовать комбинаторику:

total possible = pi(|a|_i) for all i in positions

|a|_i alphabet size at position i

and assuming all |a|_i are equal to b you have

rank of permutation = sigma(b**i * a_i)

a_i is actual alphabet character chosen at position i.

So over the 5 alphabet (ABCDE) 

The rank of AAAAA = 0 (or 1)
The rank of EEEED = 5**6 - 2

Затем, чтобы получить перестановку от ранга, просто используйте формулу радиуса: мне кажется, я помню:

a_i = (P % b**(i+1) - P & (b**i))/(b**i)

Если вы думаете об этом с этой комбинаторной и радикальной точки зрения, вы не ошибетесь даже в более сложных случаях.Просто возьмите любой ранг и конвертируйте его в базу, соответствующую вашему алфавиту.Вы можете быть заинтересованы в Преобразовании смешанного радикала в Википедии, здесь