Click here to Skip to main content
15,867,686 members
Articles / Programming Languages / C#

Permutations in C# Using Recursion

Rate me:
Please Sign up or sign in to vote.
4.10/5 (10 votes)
15 Jun 2009CPOL3 min read 178.3K   5.1K   48   18
Calculate all permutations of a set of elements using a simple recursive algorithm
commandline.PNG

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

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

C#
/// <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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Paychex
United States 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.

Comments and Discussions

 
QuestionDetermine the number of text characters generated. Pin
ayman_sharkawy20-Feb-14 8:13
ayman_sharkawy20-Feb-14 8:13 
QuestionDetermine the number of text characters generated. Pin
ayman_sharkawy20-Feb-14 8:12
ayman_sharkawy20-Feb-14 8:12 
Questionmy implementation using generics and evaluation function Pin
swheat17-Jun-13 8:32
swheat17-Jun-13 8:32 
QuestionNeed help in permutation Pin
Shahan Ayyub29-Jul-11 9:20
Shahan Ayyub29-Jul-11 9:20 
QuestionRe: Need help in permutation Pin
Shahan Ayyub19-Sep-11 5:14
Shahan Ayyub19-Sep-11 5:14 
AnswerRe: Need help in permutation Pin
Gary Stafford26-Sep-11 13:50
Gary Stafford26-Sep-11 13:50 
AnswerRe: Need help in permutation Pin
Shahan Ayyub26-Sep-11 23:18
Shahan Ayyub26-Sep-11 23:18 
GeneralMy vote of 5 Pin
Filip D'haene26-May-11 0:45
Filip D'haene26-May-11 0:45 
GeneralYour approach is slower....! Pin
masaniparesh13-Jul-10 3:39
masaniparesh13-Jul-10 3:39 
GeneralVote 4, don't like recursion.... Pin
ProtoBytes25-Mar-10 1:24
ProtoBytes25-Mar-10 1:24 
GeneralIts not working for below inputs Pin
MANOJ BATRA20-Aug-09 22:30
MANOJ BATRA20-Aug-09 22:30 
GeneralRe: Its not working for below inputs Pin
PIEBALDconsult16-Sep-09 13:37
mvePIEBALDconsult16-Sep-09 13:37 
GeneralSimpler implementation Pin
Ratish Philip15-Jun-09 21:47
Ratish Philip15-Jun-09 21:47 
GeneralRe: Simpler implementation Pin
Gary Stafford16-Jun-09 5:47
Gary Stafford16-Jun-09 5:47 
GeneralComment Pin
logicchild15-Jun-09 21:11
professionallogicchild15-Jun-09 21:11 
Nicely written article. It is good to see the recursion that we use in code
apply to the factorial process.
GeneralHey I've refactored your class to be more useful and even for Generic Arrays! Pin
AndyHo15-Jun-09 17:17
professionalAndyHo15-Jun-09 17:17 
GeneralRe: Hey I've refactored your class to be more useful and even for Generic Arrays! Pin
Gary Stafford16-Jun-09 5:49
Gary Stafford16-Jun-09 5:49 
GeneralRe: Hey I've refactored your class to be more useful and even for Generic Arrays! Pin
AndyHo16-Jun-09 9:22
professionalAndyHo16-Jun-09 9:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.