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

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）是循环所有可能的位置并将它们中的每一个与选定的顺序进行比较并且return 当前位置编号，如果它们相等。

在上面示例的这个范围内，循环 15 种可能的组合没什么大不了的，但是如果你增加椅子和人的范围，这种方法就远非有效。

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

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

我在示例中使用的排序只是为了提高可读性。欢迎任何排序类型的回答。

Answer 1

我建议您使用二叉搜索树。每次添加椅子时，树的每一侧都会被克隆，新选择的 B 或 G 将是唯一的区别。基本上，您克隆现有的内容，然后将 B 或 G 添加到旁边的每个条目。

编辑：请注意，这也可用于定位的 LogN 搜索。

Answer 2

分支限界（BB 或 B&B）是离散和组合优化问题以及一般实值问题的算法设计范例。分支定界算法包括通过状态 space 搜索对候选解进行系统枚举：候选解集被认为是形成一棵根部为完整集的有根树。该算法探索这棵树的分支，它们代表解决方案集的子集。在枚举一个分支的候选解之前，该分支将根据最优解的上下估计边界进行检查，如果它不能产生比算法迄今为止找到的最佳解更好的解，则将其丢弃。

分支定界法的本质是以下观察：在全枚举树中，在任何节点，如果我能证明最优解不会出现在它的任何后代中，那么就没有我需要考虑那些后代节点。因此，我可以 "prune" 该节点处的树。如果我能以这种方式修剪树的足够多的分支，我也许能够将它减少到计算上可管理的大小。请注意，我并没有忽略我修剪过的分支的叶子中的那些解决方案，在确保最佳解决方案不会出现在这些节点中的任何一个之后，我将它们排除在外。因此，分支定界方法不是启发式或近似过程，而是一种精确的优化过程，可以找到最佳解决方案。

Answer 3

My problem is to find efficient way to calculate position of possibility they choose to sit. Answers with any type of sorting are welcome. Is there any formula or more efficient way I can use to determinate position of selected possibility?

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

7男3女共有10!/(7! 3!) = 120种组合，以下是组合的一些位置：

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

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

Answer 4

按 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 ，有 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选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    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 的数量以及排列的秩，它将 return 排列。同样，这是在不必生成所有排列的情况下完成的。 （注意：我没有对输入的有效性进行任何检查）

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

Answer 5

这是一个O(n) 高效的算法。没有帕斯卡三角形 - 它会即时计算组合。我已经针对大值进行了测试，生成了组合并匹配了排名，但是如果您发现它不起作用的示例，请告诉我。

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

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

How to calculate the lexicographical rank of a given permutation

language-agnostic

algorithm

math

permutation

combinatorics