Lesson 1 - part C

Let's start with the word 'a'. For the word 'a' , how many anagrams are there?

The answer is 1!. There's is no other possible arrangement other than 'a' itself. How about 'an'?

The answer is two. This is because there are two possible arrangment for the word 'an'. It's 'an' and 'na'.

How about the word 'and'? Well, there's “and” , “adn”, “dan”, “dna”, “nad”, and “nda”. The total is 6.

Sound easy right? It's too early to be happy. This may seems easy because there are only three characters involved. What if there is 5 unique characters? Then the number of character would be 5! which is 120! It will be too large to be solve by hand. (Unless you have a lot of time!)

To rearrange the word , we should first try to split the word into smaller word by removing one character at a time. We keep on splitting the word until only one character left. This would be the base case. After that, we backtrack the recursion by adding the character you have removed in sequence. Complicated right? Look at the diagram below for better understanding.

abc → bc → c → cb → cba

abc → bc → b → bc → bca

abc → ac → c → ca → cab

abc → ac → a → ac → acb

abc → ab → b → ba → bac

abc → ab → a → ab → abc

See? This is recursion. The base case in this algorithm is when we are left with only one character. After that, we backtrack the recursion by adding the character we removed. So, in this case, we add 'b' to 'c' and then we add 'a' to “bc”. We keep on doing it for all possible combinations.

In programming, we can ensure that we produced all the possible combinations by using 'for' loop. Look at the diagram below, this is the code for producing anagrams.

I know! This look complicated but it's alright. I will guide you through this code.

The line 3 and 4 are used to as base case. So, when the word is left with only one character, then recursion stopped.

In line 6, we use the enumerate() function in order to make enumerates of each of the characters in the word. Then, we use the 'for' loop to iterate through the characters. In plain English, we could say that we are using the 'for'loop to select which character to be removed. In this case, we are going to choose the first character to be removed.

In line 7, we used the “word[:numberkey] + word[numberkey+ 1:] “ to remove the character chosen to be removed from the string. The term word[:numberkey] is used to obtained a copy of the string of characters located before the character tupled with 'numberkey'.

Let's say, if we have a string called “John” and enumerate it, we would obtained (0,”J”) , (1,”o”), (2, “h”), and (3,”n”). So, using [:2], will get us a string of “Jo”.

On the other hand, word[numberkey+1: ] is used to obtained the string containing the characters after the character tupled with 'numberkey'. So, using [3:] would get us “n”. Using the symbol + on these two strings will get us “jon”.

Continuing with line 7, we used the recursion by calling the anagram function. We use the 'for' loop in order to iterate through the results in each different combinations due to the different possible choice for removal of characters.

Each time, we received the result from the recursion, we add that result with the character that we had choosen to remove. I know! This may seems confusing but bear with me. After that, we add the string to the variable temp.

Once we filled the variable temp with all the possible combinations, we will return use the function set() in order to remove any repeating combinations which occurred due a string having the repeating characters.

Now, if you are still confuse, look at the diagrams below which show what happened to string “abcd” as it pass through the function.

Here's the backtracking.

Repeat the whole sequence but this time remove 'b' in first level 1, then repeat again with 'c' and finally 'd'