Super Basics - Permutations of Characters In A String

Today we will be looking at permutations of characters. We will highlight a bit of the problems with recursion mentioned yesterday as well as show another example of recursion.

Given a series of characters, find all possible permutations of those characters.

Permutations can seem a little unimportant as a subject for software. I personally cannot think of any reason offhand at this moment why a set of permutations would be handy in business purposes, however learning more about recursion, and application of encapsulating this in an object are worthwhile pursuits. You can find the source for this code on github in dotnet core with mstest test structures.

Brass Tacks

When creating software in a professional environment, we want to insure that we maintain Seperation of Concerns. That is that a specific methodology, library, or set of similar methodologies are contained in their own system. This is done in a variety of ways, and we will be doing that by creating a stand alone class, that receives a string as a set of characters and subsequently process these characters for permutation at instantiation and makes available the results from a read only property on the instance in question. Lets start with the class definition:

    public class StringPermutation
    {
        private List<string> permutations;
        private string permutationString;

        public List Permutations { get{
            return permutations;
        }}
    }
    

within our class we have private members representing the permutationString supplied to the instance of the class, the list collection that will contain the results of the permutation process, and a read only accessor for permutations. It is generally a good practice to insure that members that are not relevant outside of the class itself should not be mutated or accessed by external objects, hence why we have these private declarations and the read only accessor.

Once we have our class created, we will want to get this party started. By default all classes in C# get a parameter-less constructor, this changes if we provide a constructor that has a parameter or set of parameters. In this case, in order to convey that the StringPermutation class may only be used by passing in the purmutationString, we will only have one constructor with the relevant parameter. This will restrict any consumers of this class from creating an instance of the class without the constructor parameter.

    public StringPermutation(string permutationString)
        {
            this.permutationString = new string (permutationString.Distinct().ToArray());
            this.permutations = new List<string>();
            this.permutation();
        }

Here you can see that we insure that there are no duplicate characters with the Distinct() operation, and assign that to our internal property of the class. Many would argue, and I agree, seeing how this property is used; the permutationString property should also be tagged as readonly.

One thing to note: we must insure that the permutations list is instantiated, otherwise the application will attempt to add to an uninitialized object.

Once these are done we go ahead and kick off the permutation processing.

Recursing Ourselves

Now we are ready to get to the recursion of our process. Most implementations of recursion seem to follow a pattern of an entry point method which calls our recursively functioning method.

    private void permutation()
{
    permutation("", this.permutationString);
}

private void permutation(string perm, string word)
{
    if (string.IsNullOrWhiteSpace(word))
    
        
    
    else
    {
        for( int i = 0; i < word.Length; i++)
        {
            permutation(
                perm + word[i], 
                word.Length > 1 ? word.Remove(i, 1) : string.Empty
            );
        }
    }
}

As you can see, we have our recursive method that will accept the current string permutation, starting with the first character, and calls itself with the currently string in process, and the remaining characters to add to the permutation. Once we reach the end of our available characters, the escape condition adds the found permutation and escapes.

If we want to, we could expand this recursion, as we have a for loop over the initial string to cover all of the starting permutations.

In conclusion

As stated before, recursion is considered to be in the realm of “super coder” skills. However I have found that this is rarely used in production code, mostly due to readability and ease of diagnosis. Debugging a recursion can be a real chore as well. In production environments where you are attempting to diagnose real time customer facing issues, it really isn’t helpful to spend an extra chunk of time just trying to get your head around all of the loopiness of a recursive function.

I’ve also included a test datarow on the test unit for this mini project that you can uncomment to see real time execution of a recursive method chewing up all of your ram. Typically you either really want to do something more elegant, like spreading this calculation over a multi-process cloud (something i’m going to dig into at a future date) or re-engineer your solution entirely to more aptly accomplish the task with far fewer iterations.