ylvis's blog

Help me! Permutation
By ylvis, history, 7 years ago, In English

Hello everyone, I have a question. How can you tell how many different permutations a string has if it has even repeated elements?

The size of the chain is up to 100 dnd I think calculating the factorial would commonly be very long.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The number of permutations of n elements, where there are a1 copies of the first element, a2 copies of the second element, a3 copies of the third element and so on (so a1 + a2 + a3 + ... + ak = n) is:

You can preprocess all factorials up to 100, and compute the above formula.

Most likely, it will overflow even a 64-bit integer, so either you can use BigInteger for it, or I'm assuming that the problem asks for it modulo some prime (e.g. 109 + 7). In the latter case, you can use modular inverses to divide.

→ Reply