String Permutations
From charlesreid1
Skiena Chapter 7
Question 14
Write a function to find all permutations of the letters in a particular string (example: HELLO).
Enumerating
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).
Now consider the less trivial case where there are repeated letters: HELLO
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