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

Now we wish to count total number of permutations, but must discount permutations that are identical.

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

<math> \{ a \codt A, b \cdot B, c \cdot C, d \cdot D \}

Each position can hold any of the four letters, and one of the letters can be chosen twice.

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