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

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个可能的组合并没有什么大问题，但是如果您增加椅子和人数的范围，这种方法远非高效。

有没有任何公式或更有效的方法可以用来确定所选可能性的位置？请随意使用任何编程语言进行示例。

更新：我确切地知道房间里有多少把椅子、男孩和女孩。唯一的问题是找到他们选择坐的位置编号。

我在示例中使用的排序仅用于更好的可读性。欢迎使用任何类型的排序回答。

- Nicolo

---

你的位置编号是任意的。我不明白你想得到什么输出。如果我给你 GGBBBGB 的 7 个人，你期望得到什么编号？ - user1803551

所以，为了澄清，您是在寻找一种算法，它可以1. 提供所有可能的座位安排组合 2. 验证您生成的组合中的位置顺序吗？ - Michael Queue

我知道男孩和女孩的数量是已知且恒定的，但我不明白你如何排列位置。你如何从GGGBBG得到13？ - user1803551

我认为 OP 正在按字典顺序对它们进行排序。 - rajah9

听起来你可能正在寻找一个算法来“对重复排列进行排序”。 - גלעד ברקן

Answer 1

通过G的位置来确定排列的等级

示例中的排列按字典序排序; 第一个排列将所有B放在左侧，所有G放在右侧；其他排列是通过逐步将G向左移动而形成的。（类似于二进制数的上升序列：0011、0101、0110、1001、1010、1100）

要计算给定排列在这个过程中到达了多远，从左到右逐个查看字符：每当遇到一个G时，将其移动到该位置所需的排列数为(N choose 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，有4个G在6个可能的位置中，第一个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 choose K)

您可以使用例如 帕斯卡三角形来计算(N choose 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));

- m69 ''snarky and unwelcoming''

---

@Nicolo 反向操作是一个不同的问题，当然。但是，我相信你也可以倒转 (n choose k) 方法来计算这个问题。创建三角形，从底部开始，找到加起来等于排列数的最大数字，然后相应地移动 G 到正确的位置。 - m69 ''snarky and unwelcoming''

好的！ :) 我很快就会完成编写反转函数。完成后，我可以编辑您的答案吗（我只会添加反转函数片段）？由于您的答案被标记为最佳答案，其他人可能会发现反转函数有用，如果我将其添加到最佳答案中，比起使用另一个答案回答我的问题更好。再次感谢！ - Nicolo

@Nicolo 我今天稍后也会看一下它。如果你先到了，随意添加它 :-) - m69 ''snarky and unwelcoming''

哈哈！我本来想编辑你的帖子，但是收到了已经被编辑过的警告 :) 无论如何，请检查我要发布的修改内容：http://jsbin.com/cucirerada/1/edit?js,console - Nicolo

@Nicolo 好的，看起来我们正在做完全相同的事情，所以肯定是正确的 :-) - m69 ''snarky and unwelcoming''

Answer 2

我的问题是找到一种高效的方法来计算他们选择坐的位置。欢迎任何类型的排序答案。是否有任何公式或更有效的方法可以用来确定所选可能性的位置？

我将选择将配置映射到二进制的方式：B为1，G为0。

对于7个男孩和3个女孩，有10！/（7！3！）= 120种组合，以下是一些组合的位置：

GGGBBBBBBB <--> 0001111111
BBGBBGBBGB <--> 1101101101
BBBBBBBGGG <--> 1111111000

如果需要，您可以将其转换为十进制，但无论如何，它都是一对一的映射，可让您几乎立即确定位置。

- user1803551

---

这是不正确的，因为你在计算每个二进制数，而不是只计算那些包含正确数量的0和1的数。请看问题中的示例。 - m69 ''snarky and unwelcoming''

那么你如何几乎立即确定位置呢？ - m69 ''snarky and unwelcoming''

@m69 该位置是二进制位置。通过简单的替换，您几乎可以立即确定它。我认为您正在添加OP没有说明的假设。 - user1803551

@m69 或者，我可以问你OP问题的哪些部分与我的解决方案的有效性相矛盾。 - user1803551

让我重新表述一下：你写的每一个都是正确的，但你的解决方案只是将问题转化为另一个同样难以解决的问题。你如何建议将BBGBBGBBGB或者1101101101转化为期望的结果（即43），而不需要遍历所有排列组合？ - m69 ''snarky and unwelcoming''

Answer 3

这里是一个O(n)的高效算法。没有使用帕斯卡三角形，它可以即时计算组合数。我已经对大量数据进行了测试，生成了组合并匹配了排名，但如果您发现有例外，请告诉我。

http://dev-task.blogspot.com/2015/12/rank-of-n-bit-numbers-with-exactly-k.html

- Avik Paul

---

谢谢。看起来它可以提高性能，但主要的性能问题在于反向操作。是否也可能实时运行反向操作？ - Nicolo

你说得对，在反向操作中，唯一的选择是先减去大组合值以找到余数，因此应该从大组合值C(n-1,k)开始。我认为一旦计算出C(n-1,k)，较小的组合可以根据n和k的变化在迭代过程中实时推导出来。但是C(n-1,k)的值应该是可用的。 - Avik Paul

有趣。顺便问一下，你能否在这里描述答案的主要思想，而不仅仅是链接到它？这是 SO 上首选的方式。 - m69 ''snarky and unwelcoming''

Answer 4

分支定界算法（BB或B&B）是一种用于离散和组合优化问题以及一般实值问题的算法设计范例。分支定界算法通过状态空间搜索系统地枚举候选解集，将候选解集看作根节点形成一棵树。该算法探索代表解集子集的树枝。在枚举一个树枝的候选解之前，该树枝会与最优解的上限和下限估计进行比较，如果不能产生比算法到目前为止找到的最优解更好的解，则该树枝被丢弃。

分支定界算法的核心思想是: 在整个枚举树中的任何节点，如果我能够证明最优解不可能出现在其任何后代中，那么就没有必要考虑这些后代节点。因此，我可以在该节点处“修剪”树。如果我能够以这种方式修剪足够多的树枝，那么我可能能够将其缩小到一个可计算的大小。请注意，我并没有忽略我已经修剪的树枝叶子节点中的解决方案，在确保最优解不可能在这些节点中的任何一个节点时，我已将其排除在考虑之外。因此，分支定界方法不是启发式或近似处理过程，而是一种精确的优化过程，可以找到最优解。

- Michael Queue

Answer 5

我建议您使用二叉搜索树。每次添加一个椅子时，树的两侧将被克隆，并且新的选择（B或G）将是唯一的区别。基本上，您复制已有内容，然后在侧面的每个条目中添加B或G。

编辑：请注意，这也可用于对位置进行LogN搜索。

- soulsabr