通过G的位置找到排列的等级

示例中的排列按字典顺序 ;
第一个排列的左侧是所有B，右侧是G。其他排列是通过将G逐渐向左移动来进行的。
（类似于二进制数的升序：0011、0101、0110、1001、1010、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）。

用帕斯卡三角形计算（N选择K）

您可以使用例如Pascal的Triangle进行计算（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") + "<BR>");

document.write(permutationRank("GBGGBG") + "<BR>");

document.write(permutationRank("GGGGBB") + "<BR>");

document.write(permutationRank("GGBGBBGBBBGBBBBGGGGGBBBBBGGGGBGGGBGGBGBB"));

逆算法：生成排列

该算法将执行相反的操作：给定B的数量，G的数量以及排列的等级，它将返回排列。同样，无需完成所有排列即可完成此操作。
（注意：我没有对输入的有效性进行任何检查）

function permutationGenerator(boys, girls, rank) {

    var chairs = boys + girls, perm = "";

    var triangle = PascalsTriangle(chairs - 1);  // triangle[n][k] = (n choose k)

    for (var i = chairs; i > 0; i--) {

        if (i > girls) {

            var choose = triangle[i - 1][girls];

            if (rank > choose) {                 // > if counting from 1, >= if counting from 0

                rank -= choose;

                perm += 'G';

                --girls;

            }

            else perm += 'B';

        }

        else perm += 'G';                        // only girls left

    }

    return perm;



    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(permutationGenerator(2, 4, 1) + "<BR>");

document.write(permutationGenerator(2, 4, 8) + "<BR>");

document.write(permutationGenerator(2, 4, 15) + "<BR>");

document.write(permutationGenerator(20, 20, 114581417274));