### Using recursion to do permutations

**Solving problems using recursion.**

I have always had problems in understanding deep and complex recusion eventhough they all follow a common pattern that is

**There is always a base case to stop the recursion and making a recursive call on some smaller part of the solution**, I decided to set my bar high . Here are the things i set to use recursion to understand complex recursive calls .

- Solving Sudoku using Backtracking
- The Chess Knight - Queen classic
- Permutations
- More problems as I come across.

Let start with the case that allows you to select all possible combinations of all members a set. I learnt that this recursive pattern in very important to understand because the is a common pattern used in solving the problems that I mentioned above and many others like searching and solving word puzzles

**Permutation**

I define permutations as all the ways to arrange a set of items for example if you permute the word {cat} you get {cat, tac, act, atc, tca, cta}. Permutations are mathematical and if you want a deeper understanding of this then go to Permutation. in Wikepidia and read more

In the program below the program does permutation recursively . I am writing this because I feel I have started getting the power of recursion and how to solve problems with them. The truth is i understood the classical recursive examples in the university like Fibonacci ,factorials and the towers of Hanoi but when it came to complex recursive example like the one below. I got a headache in thinking recursively.

Here are the tough questions to answer when writing a program that does permutations.

- How do you just pick one element on the set and know which one to attach next?
- How do you avoid doubles and repeating each elements?
- How do you separate them?
- How do you know that all the possible combinations of the set have been made?

Here is the program written in C# that does permutations .

class Program { static void Main(string[] args) { Permutate("ABCD"); } public static void RecPermute(string permutateHolder , string itemToPermutate) { if (itemToPermutate== string.Empty) { Console.WriteLine(permutateHolder); } else { for (int i = 0; i < itemToPermutate.Length; i++) { // Get the rest of the items remaining in the set var remaining = itemToPermutate.Substring(0, i) + itemToPermutate.Substring(i+1); //Take each element from the item and do a recursive call on them RecPermute(permutateHolder + itemToPermutate[i], remaining); } } } // Wrapper for permutate function public static void Permutate(string item) { RecPermute("", item); } }Here is part of the recursive tree of the program Permutate("ABCD").It show permutations for all elements beginning with the letter A.The other elements of the set follow the same pattern.

Happy programming !

this is good post.

ReplyDeleteand you can go here

http://bantalsilikon01.blogspot.com

http://kursusinternetmarketingmurah.blogspot.com

http://bumbupecelbali.blogspot.com

tanks very much.... :)