algorithm - 如何计算给定排列的字典排序

Question

例如房间里有 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 种可能的组合并不是什么大问题，但如果你增加椅子和人的范围，这种方法就远非高效。

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

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

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

Answer 1

根据 G 的位置查找排列的秩

示例中的排列在 lexicographical order 中；第一个排列的左边是所有 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's 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    1N=6    1    6   15   20   15    6    1

Code example

Below is a simple Javascript implementation. Run the code snippet to see a few examples. The execution time is linear to the number of chairs, not to the number of possible permutations, which could be huge. (update: the code now iterates over the characters from right-to-left, so that it doesn't have to count the number of G's first.)

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));