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

Question

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

Answer 1

У вас есть элементы в массиве?

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

Rank (Х, м: п) = RankOfElement (Х [м], Х [M: N]) * Факториал (п - т) + место (Х, (т + 1): п)

Оба 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) = ранг (Х, (М + 1): п) + Σ over (y ∈ X [m: n], y < X [m]) числа комбинаций {X [m: n]} - {y}.

Answer 2

EDIT

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

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

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

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

END EDIT

Ну первое, что нужно рассматривать как базовое преобразование. Каждая перестановка находится в точке (это ранг). Подумайте о двоичном. Каков эффективный алгоритм вычисления перестановки 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) 

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