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.


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??

  • $\begingroup$ I don't understand. Are you saying that any answer involving 500-factorial is inefficient? Then if all the characters are different, there is no efficient way to find the number of permutations, since the number of permutations is 500-factorial. $\endgroup$ – Gerry Myerson Feb 2 '12 at 11:20
  • $\begingroup$ Your edit does nothing to address my question. $\endgroup$ – Gerry Myerson Feb 2 '12 at 11:47
  • $\begingroup$ It may help the OP to see this: math.stackexchange.com/questions/103377/… $\endgroup$ – NoChance Feb 5 '12 at 17:08

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!$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.