Permutations in C#

By Oct 28, 2016

Description:

Permutations in CSharp

Preferencesoft

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);
                Console.WriteLine(res);
                //advance the counter
                index[0]++;
                for (int i = 0; i < n ; i++)
                    if (index[i] >= n - i)
                    {
                        index[i] = 0;
                        index[i+1]++;
                    }
            }

        }
        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:");
            DisplayPermutations(input);         
            Console.ReadLine();
        }
    }
}

CSharp

Categories

Share

Follow


KodFor Privacy Policy