Just as I am introspecting whether there’s anything I have done that I can call ‘success’, I happened to listen to this interesting podcast on Failure in TED Radio hour. There is a lot to think about - success, impact, power - we know these attractive words and we probably have been measuring each of this using a completely wrong yard-stick. If we start thinking about the times we have failed and failed miserably, and how we have overcome some of the disastrous failures (that’s actually our success but we fail to realize it that way…), that is what prepares us for success and makes us powerful.

For those interested, below is a link to the podcast:

Hopefully, I will keep learning and continue to improve my work-in-progress project (my life) and get better every day of the project.

In the previous post, we saw how to define a binary tree. Now, that we have the tree, we need to be able to insert items into the tree. So, let us write an insert function to do that:

let insert x tree = Node (Leaf, x, tree);;

If we want to insert an element 0 into an empty tree, we just do the following:

let empty = Leaf;;
(* val empty : 'a tree = Leaf *)
insert 0 empty;;
(* - : int tree = Node (Leaf, 0, Leaf) *)

Let us try something more fun. Let’s create a tree from a list. We have worked with lists all along and it is imaginable that we would accept inputs in the form of lists, but we want to implement our algorithms (later on!..) using tree data structure. So, this function is going to be very helpful. Let’s just call the function make_tree.

let rec make_tree lst =
  let empty = Leaf in
  match lst with
  | [] -> empty
  | h::t -> insert h (make_tree t);;

Let us use our new function to create a tree from the list [0; 1; 2].

make_tree [0;1;2];;
(* - : int tree = Node (Leaf, 0, Node (Leaf, 1, Node (Leaf, 2, Leaf))) *)

Wasn’t that super easy?

Let’s talk about Binary Trees - we cannot afford to ignore binary trees after having talked about several search algorithms. We will see many more applications of this wonderful data structure, but to get started, let’s understand what they are and how to create a simple one. Again, I am going to be using OCaml as I find it intuitive and concise. Probably, I will post the equivalent C/C++ code in later posts.

A Binary Tree is a tree in which each node can have at most two children

A binary tree is just a recursive data structure with a root node and two children, which themselves could be trees or leaf nodes (that have no children). Since the children could themselves be trees, we have this recursive data structure. For example,

             node-0
	      /  \
 	     /    \
	 node-1  node-2
	  / \      / \
         /   \    /   \
       leaf leaf leaf leaf	 

is how they generally look. Here, node-0 has node-1 and node-2 as child nodes, which themselves are binary trees (as they have two (‘bi’) children). It could use used to represent many things. For example, a family tree:

            Mother
	     /  \
            /    \
       daughter  Son
                 / \
                _  daughter  

Let’s first define the type binary tree - we would call it just tree.

type 'a tree =
  | Leaf
  | Node of 'a tree * 'a * 'a tree;;

This just defines the type 'a tree - as noted in one of our earlier posts ‘a is like any - we could have integer trees, string trees, etc. that would take different type values. So, a tree could either be a Leaf or another tree composed of two child trees and a root node ('a). Now we can create a new empty tree with just a Leaf:

let t = Leaf;;
(* val t : 'a tree = Leaf *)

Or we could create a tree with a root node and two child nodes, which themselves are trees with children:

let t2 = Node (Leaf, 1, Node (Leaf, 2, Node (Leaf, 3, Leaf)));;
(* val t2 : int tree = Node (Leaf, 1, Node (Leaf, 2, Node (Leaf, 3, Leaf))) *)

I know it looks awkward, but let’s decompose it and understand. Node (Leaf, 3, Leaf) is one tree. Let’s call it C. Node (Leaf, 2, C) is the next tree - Let’s call this guy B. Node (Leaf, 1, B) is the other one. So, we have something like this:

             1
	    / \          
           /   \
	 leaf   2                  |
	       / \                 |
              /   \                | -> B
	    leaf   3       |       |
                  / \      |-> C   |
		 /   \     |       |
	       leaf leaf   |       |

In the following post, we will write a functions to interact with this structure.

Let’s write a sweet short function to generate all permutations of a list. We will be using some of the built-in functions of the OCaml List module - but these are generic and it could be implemented very easily (refer to the end of this post for sample implementations). One of them is the map function, that accepts an input function and a list and applies that function to each element of the list. For example, if we want to square each element of an input list lst, call the function sq_lst:

let sq_lst lst = List.map (fun x -> x * x) lst;;

When we provide the function with a list [1;2;3], we would obtain [1;4;9] as the result.

sq_lst [1;2;3];;
(* - : int list = [1; 4; 9] *)

Another built-in function from the List module we would use is flatten, which just flattens a list of lists into a list. For example, if we want to flatten [[1; 2]; [3; 4]; [5]] into a single list:

List.flatten [[1; 2]; [3; 4]; [5]];;
(* - : int list = [1; 2; 3; 4; 5] *)

Let’s focus back at the problem at hand - generating permutations of a list.

Permutation - all possible arrangements of a list of items, where order is important.

For example, {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a} are permutations of {a,b,c}. Let’s approach this problem by first writing a function - let’s call it insert that would take two arguments - an element x to insert and a list lst to insert x into. And this function insert would insert x at all possible positions in lst. For example, if we have a list [1;2] and an element 0, we want to insert this 0 at all possible positions in the list [1;2], producing [[0; 1; 2], [1; 0; 2], [1; 2; 0]] - note that this is not the permutation, we are just inserting a given element into all possible positions in the list.

let rec insert x lst =
  match lst with
  | [] -> [[x]]
  | h::t -> 
    (x::lst) :: (List.map (fun el -> h::el) (insert x t));;

Since we are producing a list of lists as output, for the base case we create a list of list containing a single element - the input element x. The second part just applies the function to each element of the list, besides adding the element to the list itself. So, x::lst produces [0; 1; 2], and the map part produces [1; 0; 2] (which is applying the function to the first element 1 of the list (h::el) - the function just adds the element 0 to the list head item 1 giving 1; 0) and similarly [1; 2; 0].

Now we will use this insert function to write our perm (for permutation) function, which is straight-forward given the insert function. We will just traverse the list and choose each item in the list and insert the item to all the positions of the rest of the list.

let rec perm lst =
  match lst with
  | [] -> [lst]
  | h::t -> 
    List.flatten (List.map (insert h) (perm t));;

perm [0;1;2];;
(* - : int list list = *)
(* [[0; 1; 2]; [1; 0; 2]; [1; 2; 0]; [0; 2; 1]; [2; 0; 1]; [2; 1; 0]] *)

Hope this was the most intuitive way to a permutation function.

Here’s a sample implementation of map and flatten functions - I creatively named them mapp and flatn:

let rec mapp f lst =
  match lst with
  | [] -> []
  | h::t -> f h :: (mapp f t);;

let flatn lst =
  let rec aux acc l =
    match l with
    | [] -> acc
    | h::t -> aux (acc @ h) t
  in
  aux [] lst;;

In one of the earlier posts we saw a straight forward way to find the minimum missing natural number in a list. That solution, although very straight forward, required us to sort the list before finding the minimum missing number. The question was - can we get away without that expense of sorting that list?

The answer seems to be yes. Since we know that we are not allowing any duplicates and we consider only natural numbers, we can use a very nice property:

In a perfectly consecutive sequence of natural numbers, any chosen number is also the number of natural numbers less than it.

That is, if we consider the consecutive sequence of number 0 1 2 3 4 5 and choose 3, we see that there are exactly three natural numbers before it - 0 1 2. A curious mind would have noted that these three numbers actually need not be in order - they should just exist. For example 1 0 2 3 4 5 has three numbers before 3, they are not in sequence, but the fact that there are three of them assures us that nothing less than three is missing in the sequence. This is the property we are going to use to come up with a simpler search. Just like how we partitioned a list of numbers around a pivot element for quicksort, we will choose an element x and push all the numbers less than it (in any order) to the left of it and the rest to the right of it. We will also need to keep track of the number of elements num to the left of the chosen number (in order to check our fancy property mentioned above). Let’s write the partition function first:

let partition x lst = 
  let aux (num, left, right) y = 
    if (y < x) then num+1, y::left, right
    else num, left, y::right
  in
  List.fold_left aux (0, [], []) lst;;

If the number of elements tracked is equal to the chosen number, it just means that there is no missing number in the left partition (just like the example above where the number of elements less than 3 is equal to three, and we don’t have any missing natural number to the left of 3). Now, we will use this partition function to find the missing natural number:

let min_missing_num lst =
  (* m is the least nat number - 0 *) 
  let rec find_min m l = 
    match l with
    | [] -> m  (* we return 0 as the missing num *)
               (* as it is the least nat num *)
    | h::t -> 
      let (num, left, right) = partition h t in
      (* if (num = h) left side is perfect *)
      (* search on the right partition *)
      if (num + m = h) then find_min (h+1) right
      else find_min m left
    in
    find_min 0 lst;;

Think of m as the accumulator - we know that 0 is the first natural number, so in case our input list is an empty one (base case), we just return the first (minimum) natural number that is missing. Is there too much going on in this? If you could work this out in a sample input, say [0; 3; 2; 9; 1] it would help understand it better.