12,550,735 members (48,339 online)
alternative version

108.6K views
45 bookmarked
Posted

Permutations in C# Using Recursion

, 15 Jun 2009 CPOL
 Rate this:
Calculate all permutations of a set of elements using a simple recursive algorithm

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>");

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 }.

```/// <summary>
/// Algorithm Source: A. Bogomolny, Counting And Listing
/// All Permutations from Interactive Mathematics Miscellany and Puzzles
/// http://www.cut-the-knot.org/do_you_know/AllPerm.shtml, Accessed 11 June 2009
/// </summary>
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
• Initial version

Share

 Software Developer (Senior) Paychex United States
I am a senior software developer, architect, and project manager, specializing in .NET, JavaScript, Java, and database development, and build automation. I am currently a Lead Developer (.NET) / Developer IV for Paychex Enterprise Business Solutions. Paychex (PAYX) provides payroll, human resources, and benefits outsourcing and web-based solutions to business.

Prior to Paychex, I served as Lead Software Engineer, Operations Manager, and Technical Product Manager at Bio-Optronics. Bio-Optronics develops, deploys and operates information technology solutions to help healthcare professionals manage and optimize workflow to enhance quality, productivity, and patient and staff satisfaction and safety. Previously, I held positions of President, COO, Chief Technology Officer (CTO), and SVP of Technology for Lazer Incorporated. Lazer is a successful, digital imaging and Internet-based content management services provider.

You may also be interested in...

 Pro Pro

 First Prev Next
 Determine the number of text characters generated. ayman_sharkawy20-Feb-14 8:13 ayman_sharkawy 20-Feb-14 8:13
 Determine the number of text characters generated. ayman_sharkawy20-Feb-14 8:12 ayman_sharkawy 20-Feb-14 8:12
 my implementation using generics and evaluation function swheat17-Jun-13 8:32 swheat 17-Jun-13 8:32
 Need help in permutation Shahan Ayyub29-Jul-11 9:20 Shahan Ayyub 29-Jul-11 9:20
 Re: Need help in permutation Shahan Ayyub19-Sep-11 5:14 Shahan Ayyub 19-Sep-11 5:14
 Re: Need help in permutation Gary Stafford26-Sep-11 13:50 Gary Stafford 26-Sep-11 13:50
 Re: Need help in permutation Shahan Ayyub26-Sep-11 23:18 Shahan Ayyub 26-Sep-11 23:18
 My vote of 5 Filip D'haene26-May-11 0:45 Filip D'haene 26-May-11 0:45
 Your approach is slower....! masaniparesh13-Jul-10 3:39 masaniparesh 13-Jul-10 3:39
 Vote 4, don't like recursion.... TheArchitectmc∞25-Mar-10 1:24 TheArchitectmc∞ 25-Mar-10 1:24
 Its not working for below inputs MANOJ BATRA20-Aug-09 22:30 MANOJ BATRA 20-Aug-09 22:30
 Re: Its not working for below inputs PIEBALDconsult16-Sep-09 13:37 PIEBALDconsult 16-Sep-09 13:37
 Simpler implementation _Ratish_Philip_15-Jun-09 21:47 _Ratish_Philip_ 15-Jun-09 21:47
 Re: Simpler implementation Gary Stafford16-Jun-09 5:47 Gary Stafford 16-Jun-09 5:47
 Comment logicchild15-Jun-09 21:11 logicchild 15-Jun-09 21:11
 Hey I've refactored your class to be more useful and even for Generic Arrays! AndyHo15-Jun-09 17:17 AndyHo 15-Jun-09 17:17
 Re: Hey I've refactored your class to be more useful and even for Generic Arrays! Gary Stafford16-Jun-09 5:49 Gary Stafford 16-Jun-09 5:49
 Re: Hey I've refactored your class to be more useful and even for Generic Arrays! AndyHo16-Jun-09 9:22 AndyHo 16-Jun-09 9:22
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Oct-16 16:17 Refresh 1