1
$\begingroup$

Question:: Suppose We are given a string(Word),How do we efficiently find the Number of Distinct(Unique) permutaions of the given string?? As answer can get huge, print it modulo 10^9 + 7.

Constraints::

string contains only letters,both uppercase and lowercase (a/A to z/Z )

1<=|length of string|<=500

and Assume that no character repeats more than 10 times in the string.

Ex: s=aabcba The easiest way to find Number of distinct perm.=(6!)/(3!)(2!)(1!)

But suppose length of S is 500. Then to find the numb of distinct perm(programatically) in such case wont be easy as factorial of 500 can be very large..

Thus what is the efficient way to find the Number of Distinct(Unique) permutaions of the given string??

  • 0
    It may help the OP to see this: http://math.stackexchange.com/questions/103377/how-to-reverse-the-n-choose-k-formula2012-02-05

2 Answers 2

1

Assuming that you want an exact value, you can use the ideas presented in Binomial Coefficient for Large Numbers (See section: Binomial coefficient in programming languages) or use the following simple procedure if at least 1 repetition is very large compared to the total string length.

The suggested method aims at reducing the size of numbers

$K = L!/(r1!*r2!*...*rm!)$

where L is the string length and r1, r2 are the individual repetitions of each character.

for example in 300 long string with repetitions of 70, 29, 10,

We know that

$K = 300!/70! 29! 10!$

to do the calculation, you can do this:

find the max rm (70 in this case)

write L! as follows: 300! = (300 * 299 * 298 * ... * 71) * 70!

$ K = (300 * 299 * 298 * ... * 71) / 29!10!$

1

If you accept formulas that involve factorials of large numbers, then the formula that got you the answer for your length 6 example is an efficient way for all lengths.

If you don't accept formulas that involve factorials, then there is no efficient way, since, e.g., if all 500 characters are different, the number of permutations is 500-factorial, and if there are 250 of one kind and 250 of a second kind, the answer is $(500)!/((250)!)^2$.

If this doesn't answer your question, you will have to do a better job of explaining what is "efficient" and what isn't.