Permutations in C#

By Oct 28, 2016


Permutations in CSharp


In this article, we propose a program in C# to generate all possible permutations of a string. For example, consider the string ABC. A permutation ABC is obtained by optionally changing the position of the letters A, B and C relative to each other. We obtain:

  • ABC
  • ACB
  • BAC
  • BCA
  • CAB
  • CBA

To generate all permutations of the n numbers 0,1,2, ..., n-1, we cannot vary n variables of an array in any way between 0 and n-1.

In fact, it should not be that some numbers are repeated several times.

Moreover, it is forbidden to generate several times the same permutation.

To create a permutation, we declare an array of n integers acting as a counter from 0 to n! - 1.

For each natural number (), the nth cell of this array represents the new position of nth ?symbol.

To place the symbol, we use another array called free indicating locations which remain free.

using System;

namespace Permutations
    class Program

        static void DisplayPermutations(string s)
            int n = s.Length;
            int[] index = new int[n + 1];
            for (int i = 0; i < n + 1; i++)
                index[i] = 0;
            int[] free = new int[n];
            //free indicates the remaining slots available
            char[] permutation = new char[n];
            while (index[n] == 0)
                for (int i = 0; i < n; i++)
                    free[i] = i;
                for (int p=0; p<n; p++)
                    //put the pth char of the string to the right place
                    permutation[free[index[p]]] = s[p];
                    //left shift
                    for (int q = index[p]; q < n - 1; q++)
                        free[q] = free[q+1];
                string res = new string(permutation);
                //advance the counter
                for (int i = 0; i < n ; i++)
                    if (index[i] >= n - i)
                        index[i] = 0;

        static void Main(string[] args)
            Console.WriteLine("Enter a string in which all characters are distinct");
            string input = Console.ReadLine();
            Console.WriteLine("All the permutations:");