置换排名算法 [英] Permutation rank algorithm

问题描述

我在努力寻找有效的算法计算置换的秩，反之亦然（置换对于给定的等级）。有人可以给些指点？

I'm struggling to find efficient algorithm for calculating the rank of a permutation, and vice versa (permutation for a given rank). Can someone give some pointers?

推荐答案

你有数组中的重复元素？下面的工作，如果有只使用元素。

Do you have repeating elements in the array? The following works if there are only using elements.

使用下面的递归计算X的顺序[M：N]为（N-M + 1）的长度排列：

Use the following recursion calculates the order of X[m:n] as a (n-m+1) length permutation:

排名（X，M：N）=（rank_of_element（X [M]，X [M：N]）-1）*因子（NM）+秩（X，（M + 1）：N）

Rank(X,m:n) = ( rank_of_element(X[m],X[m:n]) -1 ) * factorial(n-m) + Rank(X,(m+1):n)

假设等级从0开始。

基本上，如果你有一个字符串EDCBA与E（即EABCD）+等级DCBA的开始作为一个四个字母串第一要素，那么排名（EDCBA）=排名。

Basically, if you have a string EDCBA, then Rank(EDCBA) = Rank of first element starting with E (i.e. EABCD) + Rank of DCBA as a four letter string.

这可以扩展到非唯一的情况下，但第一项需要进行更新：

This can be extended to non unique cases, but the first term needs to be updated:

秩（Ⅹ中，m:n）=秩（X，第（m + 1）中，n）+ \ sum_（y的在X [M：N]满足y＆其中，X [米]）的组合数对{X [M：N]} - {Y}

Rank(X,m:n) = Rank(X,(m+1):n) + \sum_(for y in X[m:n] such that y < X[m]) number of combinations of {X[m:n]}-{y} .

这篇关于置换排名算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！