如何计算给定排列的词典顺序 [英] How to calculate the lexicographical rank of a given permutation
问题描述
例如，房间里有6张椅子，有4个女孩和2个男孩.他们可以坐在椅子上6!/(4!*2!)=15的方式有15种.
For example there are 6 chairs in the room and there are 4 girls and 2 boys. There is 15 unique possible ways they can sit on this chairs 6!/(4!*2!)=15.
我的问题是找到一种有效的方法来计算他们选择坐下的可能性的位置.按职位，我的意思是:
My problem is to find efficient way to calculate position of possibility they choose to sit. By position I mean following:
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)的解决方案是循环所有可能的仓位，并将每个仓位与所选订单进行比较，如果存在则返回当前仓位号相等.
For example they choose position GBBGGG... For now my solution to calculate number of this position (#6) is to loop all possible positions and compare each of them to selected order and return current position number if they are equal.
在上述示例的此范围内，以15种可能的组合进行循环并不是什么大问题，但是如果您增加椅子和人员的范围，则此方法远没有效率.
In this range from example above, it's not a big deal to loop in 15 possible combinations, but if you increase range of chairs and people, this method is way far from efficient.
我可以使用任何公式或更有效的方法来确定所选可能性的位置吗?随意在示例中使用任何编程语言.
Is there any formula or more efficient way I can use to determinate position of selected possibility? Feel free to use any programming language in your examples.
更新:我确切知道房间里有多少把椅子，男孩和女孩.唯一的问题是找到他们选择坐的可能性的位置编号.
UPDATE: I know exactly how many chairs, boys and girls are in the room. Only problem is to find position number of possibility they choose to sit.
我在示例中使用的排序仅出于更好的可读性.欢迎使用任何类型的答案.
Sorting I'm using in my example is for better readability only. Answers with any type of sorting are welcome.
推荐答案
通过G的位置查找置换的排名
示例中的排列顺序为词典顺序；第一个排列的左侧是所有B，右侧是G.其他排列是通过将G逐渐向左移动来进行的. (类似于二进制数的升序:0011、0101、0110、1001、1010、1100)
The permutations in the example are in lexicographical order; the first permutation has all the B's on the left and the G's on the right; the other permutations are made by gradually moving G's to the left. (Similar to a rising sequence of binary numbers: 0011, 0101, 0110, 1001, 1010, 1100)
要计算给定排列在此过程中进行的距离，请从左到右逐个查看字符:每当遇到G时，移动它所需要的排列数就是(N选择n)其中N是当前位置右侧的位置数量，K是G的左侧数量(包括当前G).
To count how far into this process a given permutation is, look at the characters one by one from left to right: whenever you encounter a G, the number of permutations needed to move it there is (N choose K) where N is the number of positions to the right of the current position, and K is the number of G's left, including the current 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)
123456 ← positions
BBGGGG ← rank 0 (or 1)
BGBGGG ← rank 1 (or 2)
BGGBGG ← rank 2 (or 3)
BGGGBG ← rank 3 (or 4)
BGGGGB ← rank 4 (or 5)
GBBGGG ← rank 5 (or 6)
GBGBGG ← rank 6 (or 7)
GBGGBG ← rank 7 (or 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).
E.g. for GBGGBG in your example, there are 4 G's in 6 possible positions, and the first G is at position 1, so we count (6-1 choose 4) = 5; the second G is at position 3, so we add (6-3 choose 3) = 1; the third G is at position 4, so we add (6-4 choose 2) = 1; the last G is at position 6, so it's in its original position and can be ignored. This adds up to 7, which means the permutation has rank 7 (or 8 if you start counting from 1, like you do in the question).
使用帕斯卡三角形计算(N选择K)
您可以使用例如帕斯卡三角形进行计算(N选择K).这是一个三角形数组，其中每个数字是其上方两个数字的和:
You can use e.g. Pascal's Triangle to calculate (N choose K). This is a triangular array where each number is the sum of the two numbers above it:
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的第一个字符.)
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的数量以及排列的等级，它将返回排列.同样，无需完成所有排列即可完成此操作. (注意:我没有对输入的有效性进行任何检查)
This algorithm will do the inverse: given the number of B's, the number of G's, and the rank of the permutation, it will return the permutation. Again, this is done without having to generate all the permutations. (note: I have not included any checking of the validity of the input)
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));
这篇关于如何计算给定排列的词典顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
