Thursday, 4 July 2013

Permutation Problem

Permutation :
Suppose you want to arrange your books on a shelf. If you have only one book, there is only one way of arranging it. Suppose you have two books, one of History and one of Geography.
You can arrange the Geography and History books in two ways. Geography book first and the History book next, GH or History book first and Geography book next; HG. In other words, there are two arrangements of the two books.
Now, suppose you want to add a Mathematics book also to the shelf. After arranging History and Geography books in one of the two ways, say GH, you can put Mathematics book in one of the following ways: MGH, GMH or GHM. Similarly, corresponding to HG, you have three other ways of arranging the books. So, by the Counting Principle, you can arrange Mathematics, Geography and History books in3*2=6 ways.

For ex: Permutation of cat
atc
act
cat
cta
tca
tac

Let start with a Programming 
Following are the important things should be consider very important for doing a Permutation logic

1. Same combinations of words cant be repeated 
2. Logic should not check the existence of word in collection whether it is already created.
3. Effective Logic , should be created

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Permutation
{

    class RandomWord
    {
        public int GeneratedWords { private setget; }

        private string _word;

        private List<string> randomword = new List<string>();

        public RandomWord(string word)
        {
            _word = word;
        }

        public List<stringGenerateRandomWord()
        {
            GeneratedWords++;
            randomword.Add(_word);          
             GenerateWord(_word, 0false);
             return randomword;
        }

        public void GenerateRandomWord(bool printconsole)
        {
            Console.WriteLine();
            Console.WriteLine("*******************");
            Console.WriteLine(_word);
            GeneratedWords++;
            GenerateWord(_word, 0, printconsole);
        }
      
        private void GenerateWord(string word, int i,bool printconsole)
        {
            List<string> temp = new List<string>();          
            temp.Add(word);
            for (int j = i+1;  j <_word.Length; j++)
            {              
                temp.Add(Swap(word, i, j));
                GeneratedWords++;
                if(printconsole)
                Console.WriteLine(Swap(word, i, j));
                else
                randomword.Add(Swap(word, i, j));
            }

            if (i + 1 < word.Length)
            {
                foreach (string dyn in temp)
                {
                    GenerateWord(dyn, i + 1, printconsole);
                }              
            }
            temp.Clear();
            temp = null;
        }

        private string Swap(string word, int fromint to)
        {
            char []array = word.ToArray();
            char temp =  word[from];
            array[from] = array[to];
            array[to] = temp;
            return new string(array);          
        }

    }

    class Permutation
    {
        static void Main(string[] args)
        {
            start :
            Console.WriteLine("Please enter a Word");
            string word = Console.ReadLine().Trim();
            int Length = word.Length;
            DateTime start = DateTime.Now;

            RandomWord rand = new RandomWord(word);  
          
            /* Print the Random word with in the method  at the time of generation itself */
            //rand.GenerateRandomWord(true);
          
            /* Print the Random word from returned collection of GenerateRandomWord */
            List<string> words = rand.GenerateRandomWord();
            DateTime end = DateTime.Now;
             int i = 1;

            foreach (string h in words)
            {
                Console.WriteLine(" "+i.ToString()+"\t"+h);
                i++;
            }



            Console.WriteLine();
            Console.WriteLine("*********************************************");
            Console.WriteLine("* Word \t\t\t:   {0}",word);
            Console.WriteLine("* Length \t\t:   {0}", Length);
            Console.WriteLine("* Start Time \t\t:   {0} ", start);
            Console.WriteLine("* End Time \t\t:   {0} ", end);
            Console.WriteLine("* Generated Words \t:   {0}", rand.GeneratedWords);
            Console.WriteLine("* Time Taken \t\t:   {0}", end - start);
            Console.WriteLine("************************************************");

            Console.ReadLine();
            Console.Clear();
            goto start;        
        }
    }
}

This the Logic for Permutation, Which is more effective and fast genration of Permutation words.

No comments:

Post a Comment