CODEWITHSUNDEEP
algorithmmathlanguage-agnosticpermutationcombinatorics
Nicolo
Nicolo

Reputation: 1650

How to calculate the lexicographical rank of a given permutation

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

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.

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.

Upvotes: 9

Views: 3623

Answers (5)

m69 ''snarky and unwelcoming''
m69 ''snarky and unwelcoming''

Reputation: 12324

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

Upvotes: 8

Avik Paul
Avik Paul

Reputation: 76

Here is an O(n) efficient algorithm. No pascals triangle - it computes the combinations on the fly. I have tested against large values, generating the combinations and matching the ranks, yet if you find an example it does not work, let me know.

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

Upvotes: 2

user1803551
user1803551

Reputation: 13427

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?

I will pick the mapping of configuration to binary: B is 1 and G is 0.

For 7 boys and 3 girls there are 10!/(7! 3!) = 120 combinations, here are some positions of combinations:

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

You can convert to decimal if you need to, but in any case it's a 1 to 1 mapping which allows you to determine the position almost immediately.

Upvotes: 3

Michael Queue
Michael Queue

Reputation: 1400

Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as general real valued problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

The essence of the branch-and-bound approach is the following observation: in the total enumeration tree, at any node, if I can show that the optimal solution cannot occur in any of its descendents, then there is no need for me to consider those descendent nodes. Hence, I can "prune" the tree at that node. If I can prune enough branches of the tree in this way, I may be able to reduce it to a computationally manageable size. Note that, I am not ignoring those solutions in the leaves of the branches that I have pruned, I have left them out of consideration after I have made sure that the optimal solution cannot be at any one of these nodes. Thus, the branch-and-bound approach is not a heuristic, or approximating, procedure, but it is an exact, optimizing procedure that finds an optimal solution.

Upvotes: 2

soulsabr
soulsabr

Reputation: 904

I would recommend you use a binary search tree. Every time you add a chair each side of the tree will be cloned and the new choice of either B or G will be the only difference. Basically, you clone what you have and then add B or G to each entry on the side.

EDIT : Note that this can be used for a LogN search of the positioning as well.

Upvotes: 1

Related Questions