Finding the rank of a permutation by position of G's
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)
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 ← 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)
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).
Calculating (N choose K) with Pascal's Triangle
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
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"));
Inverse algorithm: generate permutation
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));
