Our problem statement begins with a description of a character string with each letter on a panel of its own. We are asked: how many unique ways can the panels be arranged (counting the original arrangement)? Immediately, you should be thinking: dictionaries. Not necessarily the data structure (though that will come into play later) but rather the lexicographical ordering that we associate with, say, the English dictionary. For beginners, this is a clear analogy and applies directly to our problem.

Permutations

Given a finite set of N elements, how many permutations, or possible orderings, can be produced? We will preface our mathematical definition with an example. Let's say we have the following word of length N = 3

Now in order to determine how many possible ways we can arrange the letters of ABC, consider each position in our 3-letter word as an empty space.

For the first position, we have 3 options: A, B, or C.

Now, depending on our choice in position 1, we'll have 2 letters to choose from for position 2. Regardless of our choice for the first position, we will always have N choices for position 1, N-1 choices for position 2, and so on until all positions are filled.

When all elements in the set are distinct, the number of permutations for a set of N elements is,

The distinct identifier is important, because in our problem we may have non-distinct elements (i.e., letters) in our input. In general, our input is represented as a multiset, rather than a set.

Why is this distinction important?

Consider our example above, but instead say our input is the word,

For the sake of demonstration, I'll mark the letters with numerical identifiers. Expanding all possible permutations, gives us the list of orderings:

But this isn't quite right, because the list is actually:

Removing duplicate orderings:

So actually there are only 3 possible permutations for AAB.

Multinomial Coefficient Formula

We must consider the general case of the multiset, M, where each letter appears as often as its multiplicity in M. The sum of the multiplicities in M is equal to the total length, N of the input word. Now we can rephrase our problem as follows:

Given a word, length N, represented as a finite multiset, M, what is the total number of multiset permutations

This is given by the multinomial coefficient formula: n! / ((mi)! * (mi+1)! * ... * (mM)!), for i = 1 to i = M, where M is the number of distinct elements.

Implementation

Before handling any test cases, we'll use a DP (Dynamic Programming) technique to compute and store all the factorials we'll be using later in the multinomial coefficient formula. Since each word will have at most 20 letters, we compute up to the 20^th factorial and store for look up by index later.

Read the input and evaluate the multiplicity of each letter. Above we discussed the mathematical concept of a multiset, and while there is a C++ STL data structure named std::multiset<T> , we are going to use std::map<Key, T> . The reasoning here is mostly aesthetic, but also because it reduces the amount of code you need to write and keeps it simple.

There are many variations of combinatorics problems, and the key to differentiating problem types is practice!

Links

• Accepted solution (C++11)
• UVa Online Judge

C++ References

• cplusplus
• cppreference