Introduction
Recently, while searching for a method to descramble a string of characters, I came across an article by Alexander Bogomolny, entitled ‘Counting and Listing All Permutations’. The article, from Interactive Mathematics Miscellany and Puzzles, introduces three separate algorithms all capable of generating a list of permutations for a given set of elements.
To rewrite a word descrambler program in C# 3.0, originally created a number of years ago in VBA for Microsoft Excel, I used one of article’s three Java-based algorithms, the recursive algorithm, rewriting in C#. In addition, I added a few enhancements, including the ability of the recursive algorithm to apply the permutations to a string of characters, input by the user, and return each permutation of the input string back to the user.
Background
First, a quick math review. Permutations are the possible combinations of elements in a set. For example, given a set of three integers: { 0, 1, 2 }, there are six possible permutations of the three integers: { 012, 021, 102, 120, 201, 210 }. The total number of permutations of a set of elements can be expressed as 3! or n factorial, where n represents the number of elements in the set. Three elements have 3! permutations, or 1 x 2 x 3 = 6. Four elements have 4! permutations, or 1 x 2 x 3 x 4 = 24. Five elements have 120; six elements have 720, and so on. The variations add up quickly; their growth is exponential.
Note, the recursive algorithm presented by Bogomolny returns all of the permutations of a given set of elements, and does not account for duplicate elements within the set, which would in turn, produce duplicate permutations. For example, given the set of four characters { t, e, s, t }, the algorithm will return { test } twice; once for the permutation { 0123 } and once for { 3120 }. To calculate permutations with repetition of elements using C#, I recommend starting with the CodeProject article by Adrian Akison entitled ‘Permutations, Combinations, and Variations using C# Generics’.
There are many other comprehensive articles on the Internet and on CodeProject dealing with permutations. I will not repeat what has already been written. The goal of this article is to demonstrate how Bogomolny’s deceivingly simple code can produce a complete list of permutations of a given set of input characters.
Using the Code
To demonstrate the recursive algorithm, I have created a simple console application using Microsoft Visual Studio 2008. The source code for this article consists of a single class (.cs) file containing two classes. When compiled and executed, the console application asks the user to input a string of characters (alpha, numeric, or symbols). The application converts the input string to a character array and stores its length (the number of characters input).
class Program
{
static void Main(string[] args)
{
Console.Write("Input String>");
string inputLine = Console.ReadLine();
Recursion rec = new Recursion();
rec.InputSet = rec.MakeCharArray(inputLine);
rec.CalcPermutation(0);
Console.Write("# of Permutations: " + rec.PermutationCount);
}
}
Using recursion, the application then calculates each possible permutation of a set of elements given the number of characters input, as a series of integers, representing each characters initial position, starting from 0. For example, the user inputs the character string ‘ugb’, from which the application calculates the six possible permutations for three elements starting from 0: { 012, 021, 102, 120, 201, 210 }. The application then retrieves individual characters from the character array { u, g, b }, corresponding to the permutations and returns them to the user: { ugb, ubg, gub, gbu, bug, bgu }.
class Recursion
{
private int elementLevel = -1;
private int numberOfElements;
private int[] permutationValue = new int[0];
private char[] inputSet;
public char[] InputSet
{
get { return inputSet; }
set { inputSet = value; }
}
private int permutationCount = 0;
public int PermutationCount
{
get { return permutationCount; }
set { permutationCount = value; }
}
public char[] MakeCharArray(string InputString)
{
char[] charString = InputString.ToCharArray();
Array.Resize(ref permutationValue, charString.Length);
numberOfElements = charString.Length;
return charString;
}
public void CalcPermutation(int k)
{
elementLevel++;
permutationValue.SetValue(elementLevel, k);
if (elementLevel == numberOfElements)
{
OutputPermutation(permutationValue);
}
else
{
for (int i = 0; i < numberOfElements; i++)
{
if (permutationValue[i] == 0)
{
CalcPermutation(i);
}
}
}
elementLevel--;
permutationValue.SetValue(0, k);
}
private void OutputPermutation(int[] value)
{
foreach (int i in value)
{
Console.Write(inputSet.GetValue(i - 1));
}
Console.WriteLine();
PermutationCount++;
}
}
Points of Interest
As you can see, the recursive algorithm can form the foundation of an effective word descrambler. The input string ‘ugb’ represents the scrambled word ‘bug’. The use of Bogomolny's recursive algorithm to descramble words will be demonstrated in my next article.
History
- June 12, 2009 - version 1.0
