Pages

Tuesday, November 18, 2008

String combinations using Brute force algorithm.

I have received requests in the past, to post answers for my interview questions (To find my interview questions, search for the tag "interview" in the right side pane under Ram cloud).

I thought let me write this one, string combination. One can find many different implementations through iteration to the permutation and combination of string in the internet.My code below; implements Brute force algorithm to find the string combination and prints them.

[The iterative pattern for the same, is considered to be one of the tough interview questions.]

Language: C#
Compiler: .NET framework 3.5
Platform: Windows server 2008, Intel Core2Duo X64.

// ****************************************************************************
//
// Copyright (C) Global Handler. All rights reserved.
//

// ram@globalhandler.com
//
// This file implements the brute force algorithm to find the string combinations.
// Note: The code is not warranted and not tested.
//

// ****************************************************************************

namespace StringCombination
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

///
/// Functionality to find the string combinations.
///

public class StringCombo
{
#region -= Variables =-

///
/// Dictionary to hold the unique strings.
///

private Dictionary stringDictionary = new Dictionary();

#endregion -= Variables =-

#region -= Constructor =-
///
/// Constructor of
///

/// The input string.
public StringCombo(string givenString)
{
if (String.IsNullOrEmpty(givenString))
{
throw new ArgumentNullException(givenString, "The given string is either Null or Empty");
}

//Find if the given string has unique characters
if (!FindForDuplicatesInString(givenString))
{
throw new ArgumentException("The string contains duplicate characters, please enter a string with unique characters");
}

int dictLimit = FindTheFactorial(givenString.Length);

GetTheCombinationsForAString(givenString, dictLimit);

PrintTheStringCombinations();
}

#endregion -= Constructor =-

#region -= Private Methods =-

///
/// Method to find the unique string combinations.
///

/// The given string.
/// The maximum combinations.
private void GetTheCombinationsForAString(string givenString, int dictionaryLimit)
{
Dictionary dictionaryForControllingRandomValues = null;

do
{
dictionaryForControllingRandomValues = new Dictionary();

do
{
DateTime currentDate = DateTime.Now;

Random rnd = new Random((int)currentDate.Ticks);

int number = rnd.Next(0, givenString.Length); //max number is the input string length.

if (!dictionaryForControllingRandomValues.ContainsKey(number))
{
dictionaryForControllingRandomValues.Add(number, givenString[number]); //char at the given index.
}

//repeats until the count of dict reaches the input string length.
} while (dictionaryForControllingRandomValues.Count != givenString.Length);

StringBuilder sb = new StringBuilder();

foreach(KeyValuePair stringForAddingToMainDict in dictionaryForControllingRandomValues)
{
sb.Append(stringForAddingToMainDict.Value);
}

if (!this.stringDictionary.ContainsKey(sb.ToString()))
{
this.stringDictionary.Add(sb.ToString(), null);
}

//repeats until the string dictionary count reaches the maximum combinations expected.
}while(this.stringDictionary.Count != dictionaryLimit);
}

///
/// Method that finds if the given string contains unique set of characters.
///

/// The given string.
/// Result of evaluation.
private bool FindForDuplicatesInString(string givenString)
{
Dictionary duplicateCharTracker = new Dictionary();

for (int i = 0; i < givenString.Length; i++)
{
char value = givenString[i];

if (duplicateCharTracker.ContainsKey(value))
{
return false;
}
else
{
duplicateCharTracker.Add(value, null);
}
}

return true;
}

///
/// The method that prints the string output.
///

private void PrintTheStringCombinations()
{
foreach (KeyValuePair uniqueString in this.stringDictionary)
{
Console.WriteLine(uniqueString.Key);
}
}

///
/// Method that gets the factorial.
///

/// Lenght of the string.
/// The factorial value.
private int FindTheFactorial(int lengthOfString)
{
if (lengthOfString == 0)
return 0;

int factorial = 1;

for (int i = lengthOfString; i > 1 ; i--)
{
factorial *= i;
}

return factorial;
}
#endregion -= Private Methods =-
}

class Program
{
static void Main(string[] args)
{
StringCombo stringCombo = new StringCombo("abc");

stringCombo = new StringCombo(null);

stringCombo = new StringCombo(string.Empty);

stringCombo = new StringCombo("aaabc");

stringCombo = new StringCombo("12345");
}
}
}


--------------------------------------------------------------------------------
For any questions and comments, please log the comments in the blogpost or alternatively email me at ram@globalhandler.com


Adding the below approach from the comment section:

say you are given a string "abc"

now, make 2 strings (clone and combine & reverse, clone and combine)
abcabc and cbacba
read out them like
abcabc -> abc, bca and cab
cbacba -> cba, bac and acb
combine them
abc bca cab cba bac acb

You know, space is no more a constrain for devs its the parallelism that matters - all that we can do is fork two threads to read them out.

This could very well be tailored using Map/Reduce for large scale clouds and clusters.

7 comments:

Harish said...

cool cool... how much you paid for the domain?

Global Handler said...

Whoohooo, had it for a while now..but was not using the email address/domain. I have post reg. the same - office live small business.

Go to http://www.officelive.com/ and get one for free.

To access your devices remotely, without VPN or any smart card subscribe to the free https://www.mesh.com/Welcome/default.aspx

Harish said...

dude... mesh really sucks... may be later....
btw i have a question on the brute force algo... will call you sometimes...

Global Handler said...

sure do it! np

Global Handler said...

what issues do you see with mesh?

@VELU said...

There is an other way to do this ...

say you are given a string "abc"

now, make 2 strings (clone and combine & reverse, clone and combine)
abcabc and cbacba
read out them like
abcabc -> abc, bca and cab
cbacba -> cba, bac and acb
combine them
abc bca cab cba bac acb

You know, space is no more a constrain for devs its the parallelism that matters - all that we can do is fork two threads to read them out.

This could very well be tailored using Map/Reduce for large scale clouds and clusters.

Global Handler said...

Man your solution is good, please post it as a new blog post, you have the permissions to do it...