Shuffling Numbers

I recently talked about generating random numbers. What if you are given a set of numbers and asked to shuffle the numbers randomly. What are the different methods that you can think of? There is basically one method you should remember, because finally every algorithm will take you to the same basic thing, which is,

Generate a random number between 1 and n (included), where n is size of the given set. Now put the number at that position in your array in the first place. Repeat the process for the n-1 remaining places. The randomness of the shuffling here will be decided by your random number generator’s randomness.

(A method suggested by Fisher-Yates and multiple others as well. Big deal!)

That is what most algorithms to shuffle numbers are all about. You can ofcourse fine tune your method to give you your shuffled sequence in O(n). Some old algorithms tend to run for O(n*n), but those are just too stupid and you can easily figure out how to fine tune them to O(n).

Yeah, that was as simple a post as they come!

PS: I don’t have a lot of time right now to write a full-blown algorithm for some problem right now. Sorry for the gap.

Counting possible parenthesizations in Matrix Chain multiplication

Problem Statement: Given the number of matrices involved in a chain matrix multiplication, find out the number of ways in which you can parenthesize these matrices in the multiplication, i.e., you have to find the number of ways you can introduce brackets in this chain matrix multiplication. (forming groups of 2).

For example,

A x B x C can be grouped in 2 ways,

(A x B) x C

A x (B x C)

You should remember that while matrix multiplication is not commutative, it is associative. Hence both the multiplications mean the same.

How do we find the number of such parenthesizations? It becomes simple when you realize that you can derive solutions for this problem using solutions to smaller subproblems which you calculated earlier. Dynamic Programming 🙂

So for,

N=1, P(N) = 1

N=2, P(N) = 1 (easy to figure out)

N=3, P(N) = 2 (again easy)

So what we are doing here is finding out the previous solution and figuring out the different ways you can introduce one more matrix in the picture to find the next. So your function looks like,

 

I guess you understand how this is Dynamic Programming. And also the fact that this is a very simple permutations question. 🙂 Not really a programming problem.

Why did I write this post? There is a genre of DP problems known as Optimal Matrix Chain multiplication. You are supposed to find the way (out of these P(n) ways) in which the number of multiplications required will be the least. We will solve this problem in the next post.

Till then, adios! 🙂

Valid Parentheses Combinations

Problem Statement: You are given a number of pairs of parentheses. You are supposed to print all valid combinations using all these parentheses.

This question is only an example of questions where you are supposed to find all the permutations of a set of elements. I am using this question to demonstrate the method to perform all such permutations.

So how do you go about finding all permutations. Here is a great method to do so. Start with a single parentheses. Now start inserting the remaining parentheses at all the possible locations. Here is how it goes if we are given 2 pairs of parentheses.

(,),(,)    //available elements

Now constructing all possibilites:

( //start — 0

()  //inserting ) to the right in 0 — 1

)(  //inserting ) to the left in 0 — 2

()( //inserting ( to the right in 1 or left of 2 — 3

(() //inserting ( either in the middle or left of 1 — 4

)(( //inserting ( in the middle of 2 — 5

()(), ())( , )()( //inserting ) at different places in 3 — 6

(()) , ()() , )(() //inserting ) at different places in 4 — 7

)(() , )()( , ))(( //inserting ) at different places in 5 — 8

Now all you need to do is find the valid combinations from those generated in 6, 7 and 8. Handy technique, right?! 🙂

PS: Leave a comment if you don’t know how to check validity of parentheses combinations and I’ll write a post on that as well.