Thursday, 12 July 2018

How to write a program to find the permutations of a given string in C#(coding interview question)

I really feel challenged in solving this problem. Basically the term permutations means arranging in an unique order(I don't know anything more). I tried finding permutations on a piece of paper, quite easy to think and note them down. Then I tried to write a program for it to find permutations for as many character as we like. I figured to solve the problem in the following way. Hope it will help you learn something. There is fiddle link below. Run it and know how it works.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
public static void Main(string[] args)
{
var stringText = "ABCD";
var possibilities = GetPossibilities(stringText);
Console.WriteLine("The permutations of *{0}* are as shown below:", stringText);
foreach (var pos in possibilities)
{
Console.WriteLine(">>>>>>>>>>>>>>" + pos + "<<<<<<<<<<<<<<");
}
}

private static List<string> GetPossibilities(string text)
{
bool reached = false;
List<string> possibleStrings = new List<string>();
List<int> possibleInts = new List<int>();
var textArray = text.ToArray();
string prev = string.Empty;
string dummy = string.Empty;
int preIndexNum = 1;
while (!reached)
{
var indexes = GetDigitsList(preIndexNum);
foreach (var index in indexes)
{
dummy = dummy + textArray[index - 1];
}
bool isPermutation = CheckPermutation(dummy, text);
if (isPermutation)
{
}
dummy = string.Empty;
reached = checkReached(preIndexNum, textArray.Length);
preIndexNum = GetNumberBasedOnTextLength(textArray.Length, preIndexNum);
}
var distinctStrings = possibleStrings.Distinct().ToList();
return distinctStrings;
}

private static bool CheckPermutation(string dummy, string text)
{
if (dummy.Count() != text.Length)
return false;
else
{
foreach (var t in dummy)
{
if (dummy.Count(x => x == t) == text.Count(x => x == t))
continue;
else
return false;
}
return true;
}
}

private static int GetNumberBasedOnTextLength(int length, int number)
{
var digitsList = GetDigitsList(number);
digitsList.Reverse();
var digitsArray = digitsList.ToArray();
var dummyIntList = new int[digitsArray.Length + 1];
for (int i = 0; i < digitsArray.Length; i++)
{
dummyIntList[i] = digitsArray[i];
}
for (int i = 0; i < dummyIntList.Length; i++)
{
if (dummyIntList[i] < length)
{
dummyIntList[i] = dummyIntList[i] + 1;
break;
}
if (dummyIntList[i] == length)
{
for (int j = i; j < dummyIntList.Length; j++)
{
if (dummyIntList[j] < length)
{
dummyIntList[j] = dummyIntList[j] + 1;
break;
}
else
dummyIntList[j] = 1;
}
break;
}
}
var list = dummyIntList.ToList();
list.Reverse();
number = GenrateNumber(list.ToArray());
return number;
}
private static int GenrateNumber(int[] digitsArray)
{
int sum = 0;
for (int i = 0; i < digitsArray.Length; i++)
{
if (digitsArray[i] == 0)
continue;
sum = sum * 10 + digitsArray[i];
}
return sum;
}
private static List<int> GetDigitsList(int number)
{
List<int> digitsList = new List<int>();
while (number > 0)
{
number = number / 10;
}
digitsList.Reverse();
return digitsList;
}
private static bool checkReached(int preIndexNum, int length)
{
var digitsList = GetDigitsList(preIndexNum);
if (digitsList.Count() == length)
{
foreach (var digit in digitsList)
{
if (digit < length)
return false;
}
return true;
}
else
{
return false;
}
}
}

To know the how the code works check this link: