String Permutations

Skiena Chapter 7

Question 14

Write a function to find all permutations of the letters in a particular string (example: HELLO).

Enumerating - Easy Case

Let's start by counting the total number of permutations of letters in a particular string.

Consider the simplest case, no repeated letters: ABCD

Each position can hold any of the four letters, but we can only choose a letter once. So the total number of permutations of a k-letter string with no repeated letters is $ k! $

Mathematically, we are picking 4 distinct objects, and we are picking all 4 objects at the same time. In other words, 4 pick 4.

This leads to a total number of possible strings:

$ P(4,4) = \dfrac{4!}{(4-4)!} = \dfrac{4!}{1} = 4! $

We are using pick, not choose, because order matters. Including a 4! on the bottom would indicate that order does not matter, and would lead to one possible outcome (obvious - any permutation with the letters ABCD will always be the same set of letters, but in different order, so there is only one outcome).

Enumerating - Multiset Case

Now consider the less trivial case where we have repeated letters: AAABCDD

To count the number of permutations of a multiset, we should use multinomial coefficients. (Note: see AOCP/Multisets and AOCP/Multinomial Coefficients).

Mathematically, this problem is what is known as a multiset problem, where we have a set of letters each occurring with some frequency:

$ \{ a \cdot A, b \cdot B, c \cdot C, d \cdot D \} $

In this case we can write the number of possible permutations by placing each character, one at a time.

Start by placing the A characters. The number of slots to place the A characters is (a) choose (number of slots):

$ \binom{a+b+c+d}{a} $

Once the As have been placed, we can enumerate the B characters The number of slots to place the B characters is (b) choose (number of slots, less A characters):

$ \binom{b+c+d}{b} $

Next, the Cs can be placed, where the number of slots to place the C characters is (c) choose (number of slots, less A and B characters):

$ \binom{c+d}{c} $

and finally, all of the other characters are placed, leaving the Ds with a single remaining configuration:

$ \binom{d}{d} $

Now, the total number of permutations is the product of each of these. The number of configurations of a multiset is given by the multinomial coefficient

$ \binom{n}{a, b, c, d} = \binom{n}{a} \binom{n-a}{b} \binom{n-a-b}{c} \binom{n-a-b-c}{d} $

More generally, for a multiset with k objects (denoted a) occurring a certain number of times (denoted r),

$ \{ r_1 \cdot a_1, r_2 \cdot a_2, \dots, r_k \cdot a_k \} $

then if there are n total slots $ r_1 + r_2 + \dots + r_k = n $, the total number of permutations is given by the multinomial coefficient,

$ \binom{n}{r_1, r_2, \dots, r_k} = \binom{n}{r_1} \binom{n-r_1}{r_2} \binom{n - r_1 - r_2}{r_3} \dots $

This can be expressed more concisely in terms of factorials:

$ \binom{n}{r_1, r_2, \dots, r_k} = \dfrac{n!}{r_1! r_2! \dots r_k!} $

Old

This is a stars-and-bars problem.

First, consider the simple case: a single letter, occurring a single time. Then we have 5 - 1 = 4 letters remaining. By placing the E at different positions in the string, we split these letters into 1 + 1 = 2 groups.

Next, consider the complicated case: a double-letter like LL. Then we have 5 - 2 = 3 letters remaining. By placing the L at different positions in the string, we split these letters into 2 + 1 = 3 groups, some of which will potentially be empty.

A generating function approach to this problem would help us determine, for large strings, how long this will take.

Now we have turned this problem into a more familiar one.

To generate the partitions: if we are partitioning k letters, we have k+1 positions.

Fencepost structure: k steps, and 1 step before or after

Actual Java implementation:

• Would ideally design this as an iterator