Weighing Stones

<< Previous Article

Puzzle #2: A 40 kg stone was being delivered to a shopkeeper. On the way, it broke into 4 pieces. When he received them, rather than becoming angry, he was happy after analyzing them. Onlookers asked, “How are you happy even after this loss?”. To that, he replied, “Now these four pieces would be useful for me in an another way. I can use them with my beam balance to be able to weigh goods of all integral denominations from 1 to 40 kgs.”

So the question is, what are the individual weights of the four pieces of the 40 kg stone?

Like Puzzle #1, this also could be solved in many ways. Try solving it yourself before proceeding further to see the analysis.

The first attempt typically done to solve any puzzle is basically to understand the puzzle, by trying to observe and register some patterns about it. Same here. Say first piece is 1 kg. Second one is 2 kgs. Then, 3 kgs could be weighed using these two. So, say the third one is 4 kg. Then, 1 + 4 = 5, 2 + 4 = 6, 1 + 2 + 4 = 7. But then, we can’t get 8 etc as the fourth piece would be 33 kgs (= 40 – 1 – 2 – 4). So, seems like 1, 2, 4 must be even more apart. O! Just hold on. In a beam balance, we can weigh not only by placing weights on one side, but on either, and moreover on both sides. For example, placing 1 kg on one side, 4 kgs on the other side would also weigh 3 kgs. Ok. Let’s restart. Say, first piece is 1 kg. Let second be 3 kgs, as 3 – 1 would anyways be able to weigh 2 kgs. Note that, making the second one as 4 kgs may not be okay, as then how do we weigh 2 kgs. Now, 1 + 3 = 4. So, for the third piece, a way could be to get 5, when the first two are subtracted from it. That is, X – (1 + 3) = 5. Then, the third one would be 9. 9 – (1 + 3) = 5, 9 – 3 = 6, 9 – 3 + 1 = 7, 9 – 1 = 8, …, 9 + 3 + 1 = 13. That seems interesting, as just with three pieces, upto 13 kgs have been achieved. But then the fourth piece would be 27 kgs (= 40 – 1 – 3 – 9). Would that serve the purpose? Check it out. Is there any pattern? Post your comments.

Now, the idea of looking into such puzzles, is not to stop after solving them. But how can these be generalized. What is the maximum weight till which all integral denominations could be weighed if there were 5 pieces of any desired individual weights? And why 5? What if it is any “n”? Can we get an answer to it? If there is a pattern, it is highly likely to get a generalized solution for any “n”. Think through it, and you’ll be amazed.

Programmers rather prefer to think in terms of programming, to solve any problem at hand, even if it is a puzzle. So, what do you think? How can it be solved programmatically? Again, don’t jump to “n”. Let’s start with the initial 40 kg stone problem itself. And once we get an idea, it could be generalized.

One approach could be to generate all 4-tuples (a, b, c, d), such that a + b + c + d = 40. We may further restrict that all of a, b, c, d are distinct. And then for each such tuple, we may check, if all integral denominations upto 40 kgs can be weighed using them. How do we check? For that, all the different placement combinations for a given tuple (a, b, c, d) have to be tried. What are the possibilities? 3 possibilities per piece: 1) Do not use it, 2) Put it on the left side of the beam balance, 3) Put it on the right side of the beam balance. Seems like 3 * 3 * 3 * 3 = 3^4 = 81 possibilities for all the 4 pieces. Not bad. It definitely can be tried using a program. Go ahead. Give it a try. You may start with an empty array of 40 elements. And keep marking, which ever weight has been achieved by any of these combinations. At the end of trying all combinations for a particular tuple, if we have been able to mark all 40 elements of the array, then the tuple is definitely one of our possible solutions.

What if we remove the particular case of not selecting any of the 4 pieces, then total combinations are 80 (= 81 – 1). And the remaining 80 are actually duplicated, e.g. putting “a” alone on left side is same as putting it alone on right side of the beam balance, and so on. So, there would be actually only 40 (= 80 / 2) unique combinations. O! That seems to hint towards the possibility of achieving all integers 1 to 40.

This is just one thought. Obviously, other interesting thoughts may be applied. And that’s the intention of this writing. Please put it down in the comments to trigger further discussions. Who knows? You may come up with an optimal algorithm.

   Send article as PDF   

Magical Pond

<< Previous Article

Decoding and solving puzzles has been there since very early days of mankind. And that has played a crucial role in the evolution of human brain. In the beginning, nature alone used to throw up puzzles for human brain to solve, for its mere existence itself. However, as human brain became more refined in thinking, analysis, and logic, it started creating its own puzzles, as well. So, today we have man-made puzzles and riddles as well, though many a times inspired from real life scenarios. Thus, inspired by the important role of puzzles in human life, and how have they been approached and solved in different ways, here is an attempt to present a semi-formal approach of logic analysis and problem solving in decoding puzzles. It would be attempted by picking up various sets of puzzles.

Puzzle #1: There is a square-shaped magic pond, which doubles the flowers dipped into it. On the four corners of the pond are four temples. A devotee comes with some flowers. She dips them in the pond. Flowers get doubled. Then, she offers some of those flowers in the first temple. She then again dips the remaining flowers in the pond. Flowers again get doubled. She then offers the same number of flowers in the second temple, as she offered in the first temple. Again the remaining flowers are doubled, and the same number of flowers are offered in the third temple, as in the second temple. And finally, the remaining flowers are doubled for the last time, and all of them are offered in the fourth temple. Interestingly, the number of flowers offered in the fourth temple is also same as that in the third temple. So, what is the minimum number of flowers the devotee would have brought, and what is the number of flowers offered in each temple?

Now, there could be many approaches to solve this puzzle. Try solving it yourself before proceeding further to see the analysis.

The first attempt typically done to solve any puzzle is basically to understand the puzzle, by trying to observe and register some patterns about it. Same here. So, one would start trying with some numbers. Say she came with 1 flower, doubled it to 2, then offered 1, and continued so forth till fourth temple. But then, if the fourth temple is also offered with 1 flower, she would have 1 flower remaining with her. So, seems like the number of flowers brought and offered can’t be same. On further delving, there would be a realization that flowers offered need to be more than flowers brought, for it to reduce on consecutive iterations. Moreover, the flowers offered need to be less than twice the flowers brought, for the same reason. Given this understanding, one may try with next set of possible numbers as 2 flowers brought and 3 flowers offered. Not working. Then, with 3 flowers brought, either 4 or 5 flowers could be offered. Interestingly, with 3 flowers brought, and 4 flowers offered, all flowers get over in the second temple itself. And with 1 flower brought, and 2 flowers offered, all flowers were getting over in the first temple itself. Wow! There seems to be some pattern.

Now, one can approach this way, and finally get a solution. But as this is a trial and error kind of approach, computers are better in solving this. And a programmatic flow can be evolved for the same. And in that case, why only for a square pond? Why not an n-sided polygon pond with n temples? Great idea. And here is how the logic for that could be laid out:

solved = false;
brought = 1;
while (!solved)
{
	for (offered = brought + 1; offered < 2 * brought; offered++)
	{
		if (solved = solve(n, brought, offered))
		{
			printf("Min Brought: %d. Offered: %d\n", brought, offered);
			break;
		}
	}
	brought++;
}

where the solve() function could be the puzzle iterator, as follows:

solve(n, brought, offered)
{
	rem = brought;
	for (i = 1; i <= n; i++)
	{
		rem = 2 * rem - offered;
	}
	return (rem == 0) ? true : false;
}

Why is the minimum number of flowers brought, is being discussed? This can be easily seen by replacing the while (!solved) by a while (1). And there would be a continuous listing of infinite solutions to this puzzle.

Furthermore, why does the magic pond only double? What if it makes it k-times? The above problem could be parameterized even for that to observe even more interesting patterns – left as an exercise for the reader.

Now, this was just one approach to solve the puzzle and without any hesitation could be called as the computer science approach.

What if one wants to do it without computer science fundae – computer science is only very recent, right? Yes, as mentioned earlier, there could be many more approaches to the problem. Computer Science is just an ease. Or, rather an approach of making ourselves easier by trying to offload our brain tasks to computers.

Just to demonstrate that there could be other approaches as well, one may take a mathematical approach using algebra to solve the same. Let ‘b’ be the (positive) number of flowers brought, and ‘o’ be the (positive) number of flowers offered. Then, using these two variables, one may form an equation as per the puzzle, and then solve it. It would turn out to be one linear equation in two variables, and hence offering infinite solutions, same as above.

Expecting an answer to the above puzzle. Just try it out and find out for yourself. And may be, using your own approach. And then don’t forget posting it below in the comment box.

Next Article >>

   Send article as PDF   

Magic Square

<< Previous Article

A magic square is a square, with n rows and n columns, and thus consisting of n2 smaller squares. Moreover, each of these squares are filled with a distinct number, such that the sum of all the numbers in a row is equal to the sum of all the numbers in any other row or column. If n is even, it may not be always possible to form such a magic square, e.g. there exists no magic square for n = 2. However, if n is odd, there are infinitely many magic squares possible for all such n. To restrict this infinitely many to a finite number, the n2 squares are typically filled with the consecutive numbers 1, 2, …, n2. Once a magic square is obtained using these numbers, then by adding any integer to all of the squares, one may obtain yet another magic square. And thus, as integers are infinite, there is an infinite number of possible magic squares for a given n.

Interestingly enough, for an odd n, there exists a simple logic to fill the numbers 1, 2, …, n2 into a n x n magic square. Consequently, the sum of any row or column turns out to be n * (n2 + 1) / 2. And the middle most number turns out to be (n2 + 1) / 2. Here is the logic to fill the numbers 1, 2, …, n2, in that order:

  • Fill 1 in middle most square of the first row
  • For every next number, follow the steps below:
    • If the current number is filled in the first row, then fill the next number in the last row, in the column just next to the current one. If it is not applicable or possible, follow the next step.
    • If the current number is filled in the last column, then fill the next number in the first column, in the row just above the current one. If it is not applicable or possible, follow the next step.
    • Fill in the row just above the current one in the just next column. If it is not applicable or possible, follow the next step.
    • Fill in the row just below the current one in the same column. If all the above fails, this will be always possible.

In a more programmatic format, it would look like this, assuming the magic square to be a 2-D array of size n x n, with its index starting from 0:

magic_square(int M[n][n])
{
	r = 0; // current row
	c = (n - 1) / 2; // current column

	for (i = 1; i <= n * n; i++)
	{
		M[r][c] = i;
		if ((r == 0) && (c < (n - 1)))
		{
			nr = n - 1;
			nc = c + 1;
		}
		else if ((c == (n - 1)) && (r > 0))
		{
			nr = r - 1;
			nc = 0
		}
		else if ((r > 0) && (c < (n - 1)))
		{
			nr = r - 1;
			nc = c + 1;
		}
		else // ((r == 0) && (c == (n - 1)))
		{
			r = r + 1;
			c = c;
			continue; // as this is always possible
		}
 		if (!isfilled(M[nr][nc]))
		{
			r = nr;
			c = nc;
		}
		else
		{
			r = r + 1;
			c = c;
		}
	}
}

On a closer observation, the statements in the first three conditionals of the first if … else above are identical with modulo n (% n), i.e. they are same as:

nr = (r - 1 + n) % n;
nc = (c + 1) % n;

and the logic of the last else in both the above if … else are identical.
Hence, the logic can be further compacted as follows:

magic_square(int M[n][n])
{
	r = 0; // current row
	c = (n - 1) / 2; // current column

	for (i = 1; i <= n * n; i++)
	{
		M[r][c] = i;
		nr = (r - 1 + n) % n;
		nc = (c + 1) % n;
 		if (!isfilled(M[nr][nc]))
		{
			r = nr;
			c = nc;
		}
		else
		{
			r = r + 1;
			c = c;
		}
	}
}

Here’s 5 x 5 magic square to understand the above logic:

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Next Article >>

   Send article as PDF   

Naturally Recursive Trees

<< Previous Article

A tree is one of the many data structures, which is naturally recursive, i.e. recursive by its design itself. A tree is made up of a so called “root” node, which has zero or more (sub)trees hanging from it, and each node would have some data &/or attributes associated with it. The subtrees give the natural recursion of lower order. And because of that, all the operations on a tree, starting from creation, can be done recursively.

A good example to understand this notion of recursion in trees is a (integer) binary search tree (BST). A (integer) binary tree is a tree with all its nodes having a maximum of two subtrees hanging from them(, and containing integer data). It would become a binary search tree, if data among all its nodes is unique, and the following conditions are satisfied for every node:

  • Every data in the node’s left subtree (if any) is smaller than node’s data
  • Every data in the node’s right subtree (if any) is greater than node’s data

The advantage of such a construction is that once the tree is created from say N given data points, searching for a specific data point, in those N data points, is very optimal – takes only log2(N) steps on an average. And that’s where the name binary “search” tree also comes from. And interestingly enough, if the tree is traversed in an inorder way, i.e. in the order of left subtree (if any), node itself, and then right subtree (if any), the data so obtained would be in the ascending sorted order.

Let B denote the binary search tree, and v any data value. Also, let B->left, B->data, B->right be the left subtree, data of the root node, right subtree, respectively of the binary search tree B. Then, the various operations of the binary search tree may be depicted recursively by recursing on the left & right subtrees, and with the actual operation in the terminating condition.

Inserting a value v in the BST B:

bst_insert(B, v) // only if v is not already there in B
{
	if (isempty(B))
	{
		setup(B); // With empty B->left and B->right
		B->data = v;
	}
	else if (v < B->data)
	{
		bst_insert(B->left, v);
	}
	else if (v > B->data)
	{
		bst_insert(B->right, v);
	}
}

Searching a value v in the BST B:

bst_search(B, v)
{
	if (isempty(B))
	{
		return false;
	}
	else if (v == B->data)
	{
		return true;
	}
	else if (v < B->data)
	{
		return bst_search(B->left, v);
	}
	else if (v > B->data)
	{
		return bst_search(B->right, v);
	}
}

Inorder Traversing the BST B:

bst_inorder(B)
{
	if (!isempty(B))
	{
		bst_inorder(B->left);
		print(B->data);
		bst_inorder(B->right);
	}
}

In case of deleting a node with a given value v from the BST B, it can again be done recursively, just that the actual deleting the node in the terminating condition, need to take care of the BST properties being maintained even after the delete. It may be depicted as follows:

Deleting the node with value v in the BST B:

bst_delete(B, v)
{
	if (!isempty(B))
	{
		if (v == B->data)
		{
			if (isempty(B->right))
			// Just connect the left subtree here
			{
				t = B;
				B = B->left;
				cleanup(t);
			}
			else if (isempty(B->left))
			// Just connect the right subtree here
			{
				t = B;
				B = B->right;
				cleanup(t);
			}
			else
			// Both subtrees are present
			// Replace by the biggest from the left subtree
			{
				B->data = get_n_delete_biggest(B->left);
			}
		}
		else if (v < B->data)
		{
			bst_delete(B->left, v);
		}
		else if (v > B->data)
		{
			bst_delete(B->right, v);
		}
	}
}

And the get_n_delete_biggest(B), used above, may be implemented (again recursively) as follows:

get_n_delete_biggest(B) // B is assumed to be never empty
{
	if (isempty(B->right))
	// "root" node itself is the biggest
	// Replace by the left subtree
	{
		v = B->data;
		t = B;
		B = B->left;
		cleanup(t);
	}
	else
	{
		v = get_n_delete_biggest(B->right);
	}
	return v;
}

Next Article >>

   Send article as PDF   

Permutations of Selections

<< Previous Article

In the previous article on permutations, the special case of arrangements of all the “n” distinct items, was dealt with. Now, with that and the logic of combinations (different ways of selecting “k” items from “n” distinct items), we are all set for the general permutations of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.

As mentioned in the previous article, the total number of such different permutations or arrangements possible can be readily computed using the following recursive relation and the terminating condition:
nPk = k * n-1Pk-1 + n-1Pk, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.

A straight away functional recursive implementation would look like this:

permutations(n, k)
{
	if (k == 0)
		return 1;
	else if (k == n)
		return k * permutations(n - 1, k - 1);
	else
		return k * permutations(n - 1, k - 1) + permutations(n - 1, k);
}

And now with the earlier two logics of printing (different possible selections of “k” items from “n” (distinct) items, and all different possible arrangements of “n” (distinct) items), it is just a matter of few tweaks to be able to invoke the above two logics to solve the general permutations printing logic.

Note that the general permutations is a two step process of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). Hence, it can be implemented recursively, using a recursive logic similar to that of the selection logic, and then applying the arrangement logic, once selected.

Assuming the print_arrangements(n, basket[]) available from the previous article, and invoking & renaming the selections() logic from its previous article, we have the following:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print_arrangements(plen, prefix);
	}
	else if (k == n)
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		// Following two recursive calls of selections_arrangements
		// have been swapped, compared to the original recursive calls
		// of selections, to print them from left to right
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

Note the change to the invocation of print_arrangements() logic, instead of just the print() logic, in the cases of k == 0 and k == n, where the selecting of “k” items from “n” distinct items is already complete and now their arrangements need to be printed.

Moreover, as the cases k == 0 and k == n, take similar action, they can be further merged as follows:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if ((k == 0) || (k == n))
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

And again, as in the previous articles, to make the toplevel call look beautiful, a wrapper print_selections_arrangements() can be provided as follows:

print_selections_arrangements(n, k, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "k" items

	selections_arrangements(n, k, basket, plen, prefix);
}

Next Article >>

   Send article as PDF   

Permutations

<< Previous Article

Once done with combinations, it is natural to jump to the next level – the permutations. Like combinations in the previous article, a lot of concepts will be similar. Though similar, the recursive relation would be definitely different. And so, the assumptions on our procedure to be existing for lower order, though similar, would have some variations. In general, permutations is a procedure of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.

If it is to just compute the total number of such different permutations or arrangements possible, mathematics as usual readily provides the recursive relation and also the terminating condition:
nPk = n-1Pk + k * n-1Pk-1, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.

Interestingly, in the case of permutations, there are two recursive relations for two different scenarios, and one terminating condition. First, let’s work out the simpler case – the arrangements of all the “n” distinct items, i.e. for the special case k = n. And as the two parameters are same, they may be merged into one, say just “n”.

A straight away functional recursive implementation would look like this:

permutations(n)
{
	if (n == 0)
		return 1;
	else
		return n * permutations(n - 1);
}

Looks familiar? Yeah! Similar to the recursive implementation of factorial. In fact, it is the same. Recall that there are n! ways of arranging “n” (distinct) items. Anyways.

What about printing all these different possible arrangements of “n” (distinct) items? Should be similar, as the recursive logic should still hold. For n = 0, i.e. arranging 0 (distinct) items, the only way is arranging nothing, and hence print nothing. Additionally, the basket of “n” (distinct) items also need to be provided as an input to the procedure, say something like arrangements(n, basket[]). So, the procedure statement can be specified as follows: Implement a procedure arrangements(n, basket[]), which takes a number “n”, and a basket of “n” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line.

Now, with all the background set to implement arrangements(n, basket[]), let’s apply the usual trick of assuming the procedure arrangements() to be already existing for a lower order. Based on our learnings so far, it is natural to take it for the lower order “n – 1”, as arrangements(n – 1, basket[] (with n – 1 items)), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line.

Next, to make “n” items to “n – 1” items in arrangements(n, basket[]), so as to apply the above assumed procedure to implement the logic for “n” items, we pick out one of the “n” items, and hence print n – 1Pn – 1 = (n – 1)! possible arrangements of the remaining “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by the first picked out item.

Now, same as in the case of selections in the previous article, this calls for change in the arrangements procedure & its logic. So, drawing from the past experience, the procedure statement can be redefined as follows: Implement a procedure arrangements(n, basket[], plen, prefix[]), which takes a number “n”, a basket of “n” items, a prefix of “plen” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix.

And accordingly, the assumption of the existence of lower order procedure becomes arrangements(n – 1, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix. Again, as in the case of selections, the lower ordering has not been applied to “plen” & prefix, as they are just the supporting parameters.

This assumed procedure can now be used, as in the earlier attempt, to implement the logic for arrangements(n, basket[], plen, prefix[]), by picking out one of the “n” items and applying on the remaining “n – 1” items, along with the picked out item being passed in the prefix. However, as here, all possible arrangements are being sought, note that even this picking out of one of the “n” items can be done in “n” different ways. And for all of those “n” different ways, the assumed procedure of lower order need to be invoked for the remaining “n – 1” items. Thus, the logic would evolve into a loop iterating for “n” times, each time picking out a different item out of the “n” items and applying the assumed procedure of lower order on the remaining “n – 1” items. Note the interesting translation of the multiplication of “n”, in the recursive relation, into a loop iterating for “n” times.

Also note that, now in this new setup with prefix, the terminating condition need to print the prefix, rather than printing nothing.

Hence, the final logic may be summarized as follows:

arrangements(n, basket[], plen, prefix[])
{
	if (n == 0)
	{
		print(plen, prefix);
		print_nl(); // print new line
	}
	else
	{
		for (i = 0; i < n; i++)
		{
			prefix[plen] = basket[i];
			remaining = basket - {basket[i]};
			arrangements(n - 1, remaining, plen + 1, prefix);
		}
	}
}

Note that, in the above logic, “remaining = basket – {basket[i]};” is not a typical programming language statement. So, it has to be appropriately converted, when putting it into any specific language implementation. One possible implementable logic for the above else part could look like this (by separating the 0th step of the for loop):

	{
		prefix[plen] = basket[0];
		arrangements(n - 1, basket + 1, plen + 1, prefix);
		for (i = 1; i < n; i++)
		{
			swap(prefix[plen], basket[i]);
			arrangements(n - 1, basket + 1, plen + 1, prefix);
		}
		// Reversing the shift due to the above swaps
		// to preserve the ordering in basket
		for (i = 0; i < n - 1; i++)
			basket[i] = basket[i + 1];
		basket[i] = prefix[plen];
	}

And again, as in the case of selections in the previous article, to make the toplevel call look beautiful, a wrapper print_arrangements() can be provided as follows:

print_arrangements(n, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "n" items

	arrangements(n, basket, plen, prefix);
}

Check out the next article for the recursive logic of the general permutations nPk.

Next Article >>

   Send article as PDF   

Combinations

<< Previous Article

Continuing with our journey into recursive procedures, different ways of selecting “k” items from “n” distinct items is an another fascinating procedure. In mathematical terms, it is denoted by nCk (read as n C k), combinations of “k” items from “n” (distinct) items.

If it is to just compute the total number of such different combinations or selections possible, mathematics as usual readily provides the recursive relation and also the terminating condition:
nCk = n-1Ck + n-1Ck-1, n > k > 0 (recursive relation)
nCk = 1, for k = n, or k = 0 (the two extremes – terminating condition)
Note that, the implicit condition on which nCk is defined is n >= k >= 0.

A straight away functional recursive implementation would look like this:

combinations(n, k)
{
	if ((k == 0) || (k == n))
		return 1;
	else
		return combinations(n - 1, k) + combinations(n - 1, k - 1);
}

What about printing all the different possible selections of “k” items from “n” (distinct) items? Should be similar, as the recursive logic should still hold. Though, in the two terminating conditions, the interpretation would be slightly different. So as to say, for k = 0, i.e. selecting 0 items from “n” (distinct) items, the only way is selecting no items, and hence print nothing. However, for k = n, i.e. selecting “n” items from “n” (distinct) items, the only way is selecting all the items, and hence print everything. Additionally, the basket of “n” (distinct) items also need to be provided as an input to the procedure, say something like selections(n, k, basket[]). So, the procedure statement can be specified as follows: Implement a procedure selections(n, k, basket[]), which takes two numbers “n” & “k”, and a basket of “n” items and prints the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line.

Now, with all the background set to implement selections(n, k, basket[]), let’s apply the usual trick of assuming the procedure selections() to be already existing for a lower order. What could be the lower order here? Two possibilities, as per the earlier mathematical recursive relation:

  1. selections(n – 1, k, basket[] (with n – 1 items)), which prints the n – 1Ck possible selections of “k” items from the “n – 1” (distinct) items in the basket, one selection per line.
  2. selections(n – 1, k – 1, basket[] (with n – 1 items)), which prints the n – 1Ck – 1 possible selections of “k – 1” items from the “n – 1” (distinct) items in the basket, one selection per line.

Now, how to make “n” items to “n – 1” items in selections(n, k, basket[]), so as to apply these two assumed procedures to implement the logic for “n” items? For that also, there are two possible ways, corresponding to the above two assumed procedures:

  1. Assume that the first item in the basket is not part of the selection, and hence print n – 1Ck possible selections of “k” items from the remaining “n – 1” (distinct) items in the basket, one selection per line.
  2. Assume that the first item in the basket is indeed part of the selection, and hence print n – 1Ck – 1 possible selections of “k – 1” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by the first item in the basket.

Thus the recursive logic sounds straight forward, and it should be just a matter of invoking the two assumed procedures. However, before proceeding forward to implement, a little closer look, reveals that the second possible way of selections(n – 1, k – 1, basket[]), expects an additional requirement than what was assumed: “…, each prefixed by the first item in the basket”. And clearly the assumed procedure cannot do it (in the current state). One may think, that before the invocation of the second assumed selections(n – 1, k – 1, basket[]), the first item may be printed, so as to create the prefix of the output from the selections(n – 1, k – 1, basket[]). But think again, and the realisation will dawn that the output from selections(n – 1, k – 1, basket[]) outputs n – 1Ck – 1 lines (not just one), each of which need to be prefixed by the first item.

That sounds tricky. How to achieve the prefixing? What if the prefixing is to be assumed to be done by the selections() procedure itself. Yes. Why not? But then it calls for a change to the selections() procedure logic itself, and it would also need the prefix to be passed to it as an input. Okay then. Let’s redefine our procedure statement. Implement a procedure selections(n, k, basket[], plen, prefix[]), which takes two numbers “n” & “k”, a basket of “n” items, a prefix of “plen” items and prints the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.

And that calls for the reworking of the assumption of the procedure selections() to be already existing for a lower order, which would now be as follows:

  1. selections(n – 1, k, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Ck possible selections of “k” items from the “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.
  2. selections(n – 1, k – 1, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Ck – 1 possible selections of “k – 1” items from the “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.

Note that the lower ordering need not be applied to “plen” & prefix, as they are just the supporting parameters. In fact, they could be anything.

Now, these two assumed procedures can be accordingly applied as follows to implement the logic for selections(n, k, basket[], plen, prefix[]):

  1. Assume that the first item in the basket is not part of the selection, and hence print n – 1Ck possible selections of “k” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix.
  2. Assume that the first item in the basket is indeed part of the selection, and hence print n – 1Ck – 1 possible selections of “k – 1” items from the remaining “n – 1” (distinct) items in the basket, one selection per line, each prefixed by “plen” items in prefix and the first item in the basket. Doesn’t this first item still look to be an odd one out. Not really. Note that the first item in the basket can be made last item of the prefix, making it of length “plen + 1”, as those two parameters could be anything.

Cool. Also, both the terminating conditions, now need to print the prefix as well.

Hence, the final logic may be summarized as follows:

selections(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print(plen, prefix);
		print_nl(); // print new line
	}
	else if (k == n)
	{
		print(plen, prefix);
		print(n, basket);
		print_nl(); // print new line
	}
	else
	{
		selections(n - 1, k, basket + 1, plen, prefix);
		prefix[plen] = basket[0];
		selections(n - 1, k - 1, basket + 1, plen + 1, prefix);
	}
}

Okay. Recursive logic done. But now, what to pass for plen and prefix, when calling the selections(), at the topmost level? That is simple. At the topmost level, in printing of the nCk possible selections of “k” items from the “n” (distinct) items in the basket, one selection per line, there is no prefix required to be printed. So, pass “plen” as 0, and an empty prefix, capable of holding at max “k” items, as that would be the max prefix possible while selecting “k” items. And to make the toplevel call look beautiful, devoid of these seemingly redundant plen and prefix, a wrapper print_selections() could be provided as follows, which may also check for the invalid values of “n” & “k”, not satisfying n >= k >= 0 (if desired):

print_selections(n, k, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "k" items

	selections(n, k, basket, plen, prefix);
}

Note: The logic above would print the selections from right to left. What would you need to print it from left to right? Post your thoughts in the comments.

Next Article >>

   Send article as PDF   

Tower of Brahma

<< Previous Article

After reverse printing a string recursively in our previous article, it is time to dive into more fascinating procedural recursion problems. And when talking about procedural recursion, how can one not talk about the famous “Tower of Brahma”, also referred as “Tower of Hanoi”. The puzzle comes from a story.

In the Kashi Vishwanath temple in India, there is a large room. It has three diamond poles, surrounded by 64 golden disks of decreasing radius from bottom to top. As the legend goes, when the Universe was created by Brahma, he created these disks and placed them all on one of the three poles in decreasing size from bottom to top. He then assigned the temple priests with the task of moving these disks from one pole to another, in accordance with the immutable rules of Brahma, since that time. The last move of the task which would move all the 64 disks to one of the other three poles would herald the end of the Universe. The rules to be followed are:

  1. Only one disk should be moved at a time.
  2. No bigger disk can be placed on a smaller disk.

In computation and logic, this puzzle is generalised to have n disks, and is referred to as “Tower of Hanoi”. For more technical information on the same, visit its Wiki Page.

Here is how to derive the recursive logic for the same. As discussed in the previous article, the first step is to have a very clear and precise statement of the procedure to be recursed. Puzzle Statement: Implement a procedure to move n disks from pole A to pole B, using an intermediate pole C, following the above two rules.

Now, the trick to derive the recursive relation logic is to assume the procedure to be already existing for a lower order, and then use it to achieve implementing the original higher order procedure. So here, assume the existence of the following: A procedure to move (n – 1) disks from pole X to pole Y, using an intermediate pole Z, following the above two rules. Again, note the similarity between this statement and the actual puzzle statement. And now use this to implement the original procedure. In original procedure, there are n disks, but a procedure is available only for (n – 1) disks. So, it can be visualised to be solved by breaking into the following steps:

  • (First) Move the (top) (n – 1) disks from pole A to (the intermediate) pole C, using pole B as an intermediate pole, following the above two rules. (using the assumed available procedure)
  • (Second) Move the largest single disk left on pole A to pole B.
  • (Last) Move the (n – 1) disks from (the intermediate) pole C to pole B, using pole A as an intermediate pole, following the above two rules. (using the assumed available procedure)

Good. Now the terminating condition. That is again simple. If there is only one disk. Or, even simpler, when there is no disk, do nothing.

Here’s the summary of the above discussion:

tob(n, A, B, C)
{
	if (n == 0)
	{
		do_nothing;
	}
	else
	{
		tob(n - 1, A, C, B);
		move(A, B); // move 1 disk from A to B
		tob(n - 1, C, B, A);
	}
}

That’s all? Such an involved puzzle. Such a simple solution. Unbelievable, right? But that’s the beauty of recursion. Seemingly complex problems, and why seemingly? Real complex problems can be solved with elegant simplicity using recursion. That’s why it is the king of all kinds of logic – closest to the way our brain operates.

For implementing & checking the above logic, one may implement the move(X, Y) procedure with the corresponding programming language constructs / functions, and try it out. A simplest implementation of the same could be just printing the step, as follows:

move(A, B)
{
	print("Move 1 disk from ", A, " to ", B, ".\n");
}

One may implement it in more hi-fi ways using graphics and what not, but the gist is the same – that the overall recursion logic remains the same.

Getting hooked into the world of elegant recursion? Keep reading as more secrets are unfolded.

Next Article >>

   Send article as PDF   

Introduction to Procedural Recursion

<< Previous Article

Like the Mathematical or more specifically the Functional Recursion as discussed in the previous two articles, one can even have procedural recursion. A procedure doesn’t refer to any function as in mathematics, but rather a set of steps or actions. Procedural Recursion is when a procedure is defined recursively. i.e. in terms of itself. Even for a procedure to be defined recursively, the need is just the recursive relation (of lower order) and the terminating condition. But unlike in functional recursion, the luxury of mathematics to get the recursive relation is not there. Rather, some logic has to be applied to get it. However, here the terminating condition(s) are comparatively easier to figure out.

Let’s take an example of printing the numbers in reverse of the order in which they are being read from the input. Now, one can always implement it using an array (static allocation) and a loop, or may be a linked list (dynamic allocation) and a loop. However, it can be more elegantly implemented using recursion. In case of recursion, the stack is implicitly available for storage. So, there is neither a need for an array nor a linked list to implement it, but just a local variable, which could be recursively stored on the stack.

It is time to derive the recursive relation for the integer reversal. And for that, the first step is to have a very clear and precise statement of the problem / procedure to be recursed. Problem Statement: Implement a procedure to reverse print n integers being read from the input. Why n? To achieve the lower order.

Now, the trick to derive the recursive relation logic is to assume the procedure to be already existing for a lower order, and then use it to achieve implementing the original higher order procedure. So here, assume the existence of the following: A procedure to reverse print (n – 1) integers being read from the input. Note the similarity between this statement and the actual problem statement. And now use this to implement the original procedure. In original procedure, there are n integers available in the input and here there is a procedure available to reverse print (n – 1) integers being read from the input. Then, how can the n integers in the input be made to (n – 1) to be able to apply this available procedure. Simple, read one integer. And obviously, store it in a variable. And then apply the available procedure, which would print the remaining (n – 1) integers in reverse and then print the (first) stored integer – thus printing all the n integers in reverse.

Good. What about the terminating condition? That is simple. If there is only one character. Or, even simpler, when there is no input, do nothing.

Here’s the summary of the above discussion:

reverse() // n
{
	if (no_more_input)
	{
		do_nothing;
	}
	else
	{
		int i;

		i = read();
		reverse(); // n - 1
		print(i);
	}
}

Looks too trivial, right? And it is, once you get hang of it. Say for implementing & checking it, one may replace the read, print, … with the corresponding programming language constructs / functions and try it out.

Hold on your breath to dive deeper into the concept of procedural recursion and to be able to apply the assumption trick more confidently in deriving a procedural recursive logic.

Next Article >>

   Send article as PDF   

Recursion with Trigonometry

<< Previous Article

Trigonometric functions like sine, cosine, … can all be computed recursively as well. As exponential in our previous article, the need is just the recursive relation and the terminating condition.

Recursive relation for sine(x) could be sine(x) = 2 * sine(x / 2) * cosine(x / 2) = 2 * sine(x / 2) * sqrt(1 – sine2(x / 2)). And accordingly, the terminating condition has to be derived for the limiting case when x is approaching zero, but not necessarily zero. And from world of limits, we have sine(x) = x for small x’s in radians. Also, on careful observation, the recursive relation has just one lower order x / 2, so the computation could be simplified as:

v = sine(x / 2);
sine(x) = 2 * v * sqrt(1 - v2);

Putting in the complete logic (say in C) would be as follows:

#define DELTA 0.001 // Depends on the desired accuracy

double sine(double x)
{
	if (fabs(x) < DELTA) // Terminating Condition
		return x;
	else
	{
		double v = sine(x / 2);
		return 2 * v * sqrt(1 - v * v);
	}
}

Similarly, cosine(x) could be recursively defined as 2 * cosine2(x / 2) – 1 with terminating condition of 1 – x2 / 2. And similarly all others.

Moreover, why only trigonometric functions, but all kind of mathematical functions having some recursive relation (with a terminating condition) can be computed using recursion.

And why only mathematical functions, but even procedural logic could be computed using recursion. Watch out for the same …

Next Article >>

   Send article as PDF