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)
            {
                possibleStrings.Add(dummy);
                possibleInts.Add(preIndexNum);
            }
            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)
        {
            digitsList.Add(number % 10);
            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: PermutationsOfString(.net fiddle)

No comments :

Post a comment