CODEWITHSUNDEEP
mathpermutation
MaxThrust
MaxThrust

Reputation: 137

Math - Find The Number Of Permutations Between Two Strings

This is not homework =). I am doing a project, that will auto generate a list of sequential computer names, and I want to add a warning, if the list is going to be a crazy long list.

I know how to find the number of permutations from say A-ZZZ, but I am have a heck of time trying to apply an inclusion-exclusion set. Here is the scenario, to keep it simple, the char set will only be A - Z, and case insensitive so "A" = "a".

The user enters the range of "ABC" to "AXE". So the only count I need is between those two. So the psudo logic would be get the full total count of A - ZZZ, then i need to exclude, everything before "ABC" and everything after "AXE".

So the question is, how do I find the count before "ABC" and after "AXE". I looked at all of my old discrete and stat math books, but nothing really fits, or gives me the right answer when plugging in the numbers (n! / n1!*n2!...). I even tried to do something like converting binary or hex to decimal, but as you know that is an epic fail =).

Thanks,

Dave

Upvotes: 0

Views: 102

Answers (1)

user4668606
user4668606

Reputation:

The simplest solution is to consider both Strings as numbers in a base-26 representation:

ABC = 26^2 * 0 + 26^1 * 1 + 26^0 * 2 = 28(base 10)
ACC = 26^2 * 0 + 26^1 * 2 + 26^0 * 2 = 54(base 10)

ACC - ABC = 54 - 28 = 26

So there is a total of 27 strings in the range [ABC, ACC].

The basic idea is using a positional numeral system with base 26 (all letters from A - Z).

There's only one problem with this approach:
It's not capable of handling empty characters as those don't follow the "default"-behavior in the sense that they can only appear as prefix.

A workaround to this problem would be to expand our value-mapping from

A = 0, B = 1, ..., Z = 25

to

empty = -1, A = 0, ..., Z = 25

While this breaks the definition of a numeral system, we're now capable of handling shorter strings as well:

magnitude([ZZ, AAA]) = AAA - ZZ + 1 = 0 - (-1) + 1 = 2

Upvotes: 1

Related Questions