CODEWITHSUNDEEP
permutation
Liondancer
Liondancer

Reputation: 16469

Number of permutations between strings

For the word "BOOKKEEPER". It's sorted representation is "BEEEKKOOPR" How can I find the different permutations of the word between "BEEEKKOOPR" and "BOOKKEEPER"?

similar example:

For "BBAA" 

AABB - 1
ABAB - 2
ABBA - 3
BAAB - 4
BABA - 5
BBAA - 6

6 - 1 = 5 So there are 5 words before "BBAA"

"BEEEKKOOPR" would be number 1. "BOOKKEEPER" would be some distance away. I'm not sure how to go about this as I believe this is a combinatorics problem and I don't have much experience with the subject.

Upvotes: 1

Views: 269

Answers (1)

Sensitive Cursors
Sensitive Cursors

Reputation: 31

You must understand what is lexicographic order, if you do not already.

The lexicographic order is a way, the alphabetical order of words is based on, the alphabetical order of the letters they are composed off. An example of this is the order of words given in a dictionary. For example in a dictionary, the word "verification" appears before "verify". This is because, the first letter that is different in both words is the 6th letter, and since 'i' comes before 'y' in the alphabet, "verification" appears before "verify".

In order to understand permutations, we can think of lexicographic order as an increasing numerical order, which is the same as the alphabetic order letters in English alphabet. For example, the permutations of numbers 1,2 and 3 in lexicographic order are 123, 132, 213, 231, 312, and 321. Similarly the example given by you, for "BBAA", all 6 permutations of A,A,B and B in lexicographic order are: AABB, ABAB, ABBA, BAAB, BABA and BBAA.

All the permutations of the letters, B, E, E, E, K, K, O, O, P and R, in a lexicographic order, will start with "BEEEKKOOPR" and ends with "RPOOKKEEEB". The permutation "BOOKKEEPER" will be somewhere in between "BEEEKKOOPR" and "RPOOKKEEEB".

In short the problem posed by you is the problem to find all the permutations of given entities (alphabets or numbers or anything else with a well defined order) in a lexicographic order. It has been a well studied problem for more than a thousand years. There are many ways to generate all permutations. If you search the web for a while you will know that. I would recommend to read "The Art of Computer Programming", by Donald Knuth, for an in-depth discussion.

One classical algorithm is based on finding the next permutation in lexicographic ordering, if it exists, and keep on doing it until the very last permutation. I found a very useful algorithm from a Toronto programer, see the link for details. Python comes with some useful functions to solve the same problem.

Going back to your example, all you have to do is to start with "BEEEKKOOPR", which is the first permutation in lexicographic order and keep on finding next permutation in a lexicographic order, until you find all.

Upvotes: 3

Related Questions