All Anagrams Wiki

We need to find All Anagrams (i.e. all possible unique combination of a sequence of characters) for example for string "ab", we can have two combinations: {ab , ba}

The idea is to create a structure similar to the Tree Data Structure in which there would be no root node and each parent node can have multiple children (not necessarily two children as with the Binary Tree).

Node structure:

• Each node has a value.
• Each node has a list of children which is a list of node.

Constructing the Tree Structure:

1. Loop through each character in the given string
2. if the node does NOT have a child with the value of the Char --> Then:
• create a new node.
• assign the char to the new node.
• append the new node to the parent node list of children.
• subtract the added char from the char sequence.
• pass the new node and the remainder of the char sequence to the recursive.

*note: (R) is the remainder of the char sequence.
Example 1: What are all anagrams of "aabb"
Traversing through the Tree Structure, Anagrams of "aabb" are: (aabb, abab, abba, baab, baba, bbaa).
The Tree structure would look like:

                                        (No root)
                   /^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\
                  b (R=aab)                                        a (R=abb)
          /^^^^^^^^^^^^^^^^^^^^\                            /^^^^^^^^^^^^^^^^^^^^^^\        
         b (R=aa)              a (R=ab)                    b (R=ab)                 a (R=bb)
         |                  /^^^^^^^^^^^^\              /^^^^^^^^^^^\               |
         a (R=a)            b (R=a)       a (R=b)       b (R=a)      a (R=b)        b (R=b)
         |                  |             |             |            |              |
         a (R=null)         a (R=null)    b (R=null)    a (R=null)   b (R=null)     b (R=null)

Example 2: What are all anagrams of "abc"
Traversing through the tree structure, Anagrams of "abc" are: (abc, acb, bac, bca, cab, cba)
The Tree structure would look like:

                                         (No root)
             /^^^^^^^^^^^^^^^^^^^^^^^^^^^^^|^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\
            c (R=ab)                       b (R=ac)                            a (R=bc)
       /^^^^^^^^^^^^^^\             /^^^^^^^^^^^^^^^\               /^^^^^^^^^^^^^^^^^^^^^^\        
      b (R=a)         a (R=b)      c (R=a)           a (R=c)       c (R=b)                  b (R=c)
      |               |            |                 |             |                        |
      a (R=null)      b (R=null)   a (R=null)        c (R=null)    b (R=null)               c (R=null)