如何计算给定排列的词典排名

例如,房间里有6把椅子,有4个女孩和2个男孩.他们可以坐在这把椅子上,有15种独特的方式6!/(4!*2!)=15.

我的问题是找到有效的方法来计算他们选择坐的可能性的位置.按位置我的意思是:

BBGGGG - possible position #1
BGBGGG - possible position #2
BGGBGG - possible position #3
BGGGBG - possible position #4
BGGGGB - possible position #5
GBBGGG - possible position #6
GBGBGG - possible position #7
GBGGBG - possible position #8
GBGGGB - possible position #9
GGBBGG - possible position #10
GGBGBG - possible position #11
GGBGGB - possible position #12
GGGBBG - possible position #13
GGGBGB - possible position #14
GGGGBB - possible position #15

例如,他们选择位置GBBGGG...现在,我计算这个位置数(#6)的解决方案是循环所有可能的位置,并将它们中的每一个与选定的顺序进行比较,如果它们相等则返回当前位置编号.

在上述示例的范围内,以15种可能的组合循环并不是什么大不了的事,但如果增加椅子和人的范围,这种方法远非有效.

是否有任何公式或更有效的方法可用于确定所选可能性的位置？您可以在示例中随意使用任何编程语言.

更新:我确切知道房间里有多少椅子,男孩和女孩.唯一的问题是找到他们选择坐的可能性的位置数.

我在我的例子中使用的排序只是为了更好的可读性.欢迎任何类型的排序答案.

根据G的位置找出排列的等级

示例中的排列按字典顺序排列 ; 第一个排列的左边是所有的B,右边的是G; 其他排列是通过逐渐向左移动G来实现的.(类似于二进制数的上升序列:0011,0101,0110,1001,11010,1100)

要计算给定排列进入这个过程的距离,从左到右逐个查看字符:每当遇到G时,移动它所需的排列数(N选择K)其中N是数字当前位置右侧的位置,K是左侧的G的数量,包括当前的G.

123456←职位
BBGGGG←等级0(或1)
BGBGGG←等级1(或2)
BGGBGG←等级2(或3)
BGGGBG←等级3(或4)
BGGGGB←等级4(或5)
GBBGGG←等级5(或6)
GBGBGG←等级6(或7 )
GBGGBG←排名7(或8)

例如,GBGGBG在你的例子中,6个可能位置有4个G,第一个G位于1位,所以我们计算(6-1选4)= 5; 第二个G位于第3位,所以我们加(6-3选3)= 1; 第三个G位于第4位,所以我们加(6-4选2)= 1; 最后一个G位于第6位,因此它处于原始位置,可以忽略.这加起来为7,这意味着排列具有等级7(如果从1开始计数,则为8,就像在问题中一样).

用Pascal的三角形计算(N选择K)

您可以使用例如Pascal的三角形来计算(N选择K).这是一个三角形数组,其中每个数字是它上面两个数字的总和:

             K=0  K=1  K=2  K=3  K=4  K=5  K=6
      N=0    1
     N=1    1    1
    N=2    1    2    1
   N=3    1    3    3    1
  N=4    1    4    6    4    1
 N=5    1    5   10   10    5    1
N=6    1    6   15   20   15    6    1

代码示例

下面是一个简单的Javascript实现.运行代码段以查看一些示例.执行时间与椅子的数量成线性关系,而不是可能的排列数量,这可能是巨大的.(更新:代码现在从右到左迭代字符,因此它不必先计算G的数量.)

function permutationRank(perm) {
    var chairs = perm.length, girls = 0, rank = 1;         // count permutations from 1
    var triangle = PascalsTriangle(chairs - 1);            // triangle[n][k] = (n choose k)
    for (var i = 1; i <= chairs; i++) {
        if (perm.charAt(chairs - i) == 'G' && ++girls < i) {
            rank += triangle[i - 1][girls];
        }
    }
    return rank;

    function PascalsTriangle(size) {
        var tri = [[1]];
        for (var n = 1; n <= size; n++) {
            tri[n] = [1];
            for (var k = 1; k < n; k++) {
                tri[n][k] = tri[n - 1][k - 1] + tri[n - 1][k];
            }
            tri[n][n] = 1;
        }
        return tri;
    }
}

document.write(permutationRank("BBGGGG") + "
");
document.write(permutationRank("GBGGBG") + "
");
document.write(permutationRank("GGGGBB") + "
");
document.write(permutationRank("GGBGBBGBBBGBBBBGGGGGBBBBBGGGGBGGGBGGBGBB"));