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

Pseudocode:

f 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");
        }
    /// <summary>
    /// Wrapper function
    /// </summary>
    /// <param name="input"></param>
    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

|-- RecPermute’’, ‘abc’

| |-- RecPermute’a’, ‘bc’

| | |-- RecPermute’ab’, ‘c’

| | | |-- RecPermute’abc’, ‘’

abc

| | | |-- return None

| | |-- return None

| | |-- RecPermute’ac’, ‘b’

| | | |-- RecPermute’acb’, ‘’

acb

| | | |-- return None

| | |-- return None

| |-- return None

| |-- RecPermute’b’, ‘ac’

| | |-- RecPermute’ba’, ‘c’

| | | |-- RecPermute’bac’, ‘’

bac

| | | |-- return None

| | |-- return None

| | |-- RecPermute’bc’, ‘a’

| | | |-- RecPermute’bca’, ‘’

bca

| | | |-- return None

| | |-- return None

| |-- return None

| |-- RecPermute’c’, ‘ab’

| | |-- RecPermute’ca’, ‘b’

| | | |-- RecPermute’cab’, ‘’

cab

| | | |-- return None

| | |-- return None

| | |-- RecPermute’cb’, ‘a’

| | | |-- RecPermute’cba’, ‘’

cba

| | | |-- return None

| | |-- return None

| |-- return None

|-- return None
*

Happy Coding 😊


Reactions

Post a Comment

0 Comments

Close Menu