Generate permutations of a given string in c#

In this post, I will show you how to generate the permutations of a given string in c#. This problem is a perfect example of the recursion technique.

What is recursion

In computer science, recursion is a programming technique using a function or algorithm that calls itself one or more times until a specified condition is met. The rest of each repetition is processed from the last one called to the first.

Pseudocode:

  • if you have no more characters left to rearrange
  • print current permutation
  • for (every possible choice among the characters left
    to rearrange){
  • Make a choice and add that character to the permutation.
    so far
  • Use recursion to rearrange the remaining letters
using System.Collections.Generic;
using System;
using System.Generic;
using System.Linq;
using System.Text;
namespace Permutation
{
	class Program
	{
		static void Main(string[] args)
		{
			Permutation("abc");
		}
		public static void Permutation(string input)
		{
			RecPermutation("", input);
		}
		private static void RecPermutation(string soFar, string input)
		{
			if (string.IsNullOrEmpty(input))
			{
				Console.WriteLine(soFar);
				return;
			}
			else
			{
				for (int i = 0; i < input.Length; i++)
				{

					string remaining = input.Substring(0, i) + input.Substring(i + 1);
					RecPermutation(soFar + input[i], remaining);
				}
			}
		}
	}
}

Recursion Tree Visualization


Happy Coding 😊

Post a Comment

Please do not post any spam link in the comment box😊

Previous Post Next Post

Blog ads

CodeGuru