Click here to Skip to main content
Click here to Skip to main content

Permutations in C# Using Recursion

, 15 Jun 2009 CPOL
Rate this:
Please Sign up or sign in to vote.
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).

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

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

Share

About the Author

Gary Stafford
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.
Follow on   Twitter

Comments and Discussions

 
QuestionDetermine the number of text characters generated. Pinmemberayman_sharkawy20-Feb-14 8:13 
QuestionDetermine the number of text characters generated. Pinmemberayman_sharkawy20-Feb-14 8:12 
Questionmy implementation using generics and evaluation function Pinmemberswheat17-Jun-13 8:32 
QuestionNeed help in permutation PinmemberShahan Ayyub29-Jul-11 9:20 
QuestionRe: Need help in permutation PinmemberShahan Ayyub19-Sep-11 5:14 
AnswerRe: Need help in permutation PinmemberGary Stafford26-Sep-11 13:50 
AnswerRe: Need help in permutation PinmemberShahan Ayyub26-Sep-11 23:18 
GeneralMy vote of 5 PinmemberFilip D'haene26-May-11 0:45 
GeneralYour approach is slower....! Pinmembermasaniparesh13-Jul-10 3:39 
GeneralVote 4, don't like recursion.... PinmemberTheArchitectmc25-Mar-10 1:24 
GeneralIts not working for below inputs PinmemberMANOJ BATRA20-Aug-09 22:30 
GeneralRe: Its not working for below inputs PinmemberPIEBALDconsult16-Sep-09 13:37 
GeneralSimpler implementation Pinmember_Ratish_Philip_15-Jun-09 21:47 
GeneralRe: Simpler implementation PinmemberGary Stafford16-Jun-09 5:47 
GeneralComment Pinmemberlogicchild15-Jun-09 21:11 
GeneralHey I've refactored your class to be more useful and even for Generic Arrays! PinmemberAndyHo15-Jun-09 17:17 
GeneralRe: Hey I've refactored your class to be more useful and even for Generic Arrays! PinmemberGary Stafford16-Jun-09 5:49 
GeneralRe: Hey I've refactored your class to be more useful and even for Generic Arrays! PinmemberAndyHo16-Jun-09 9:22 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.141022.2 | Last Updated 15 Jun 2009
Article Copyright 2009 by Gary Stafford
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid