Derangement

"Derangement" is a counting problem that commonly occurs in many puzzles, probability questions etc. I wanted to solve another counting problem, that required building upon derangements. So I brushed up on combinatorics to find a quick formula for derangement. It was so elegant, that I had to put it up here.

Derangement is such an arrangement, that no object is in its correct place. For example, if you are to create a derangement of all letters in the alphabet (A .. Z), then such an arrangement should NOT have A at the first place, and B at the second place, and so on, till Z cannot be at 26th place. There is precisely one "forbidden" spot for every object.

As an example, consider only 3 letters [A B C]. The only possible derangements for these letters are [BCA, CAB].

The question is, in how many ways you can do this for N objects ? Let's use the notation for derangement as D(N). Obviously, D(N) < N!.

This problem can be phrased in different ways.

Say N people went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, they deliberately put on a wrong name tag on their shirts. No person had the right name tag. In how many ways can they do it ?
Answer : In D(N) ways.

Another one.

Start with 2 deck of cards. Shuffle each of them separately, and put it next to each other on a table. Start picking one card from the top of each deck, compare and discard. Keep doing it till all 52 pairs have been compared. What is the probability that not a single pair had same cards ?

Answer : D(52) / 52!. Favorable outcomes divided by total number of outcomes.

But what's the formula for calculating D(N) ? It's very elegant.

Think of N numbered balls (from 1..N) to be put in N numbered bins (from 1..N). The task is to arrange N balls so that no ball is in the bin with the same number.

Start with any ball i. It cannot be put in bin i, so there are N-1 ways to choose a bin. Let's say it was put in bin k. For every such choice, following is true. We examine ball k, whose bin was chosen for ball i.

1. Either ball k was put in bin i.

2. Or ball k was NOT put in bin i.

These are mutually exclusive choices. So we can find the count of ways each can be done, and sum them up for getting final answer for D(N).

First choice, ball k was put in bin i. Just remove, the pair bin i and k, with balls k and i in them respectively. That leaves us N-2 balls to be put in an derangement. Each having exactly one forbidden spot. This is nothing but D(N-2).

Second choice, ball k is NOT to be put in bin i. Remove the bin k (with ball i in it). And rename the bin i to bin k, as the ball k is NOT to be put in it. That leaves with N-1 balls to be put in derangement. Each having exactly one forbidden choice. This is nothing but D(N-1).

So for every choice of k, there are D(N-1) + D(N-2) possible number of derangements. Since there are (N-1) choices for k, the formula is

D(N) = (N-1) * ( D(N-1) + D(N-2) )

This formula is very similar to Fibonacci numbers ! But the multiplication makes it grow really faster than Fibonacci sequence.

By defining D(0) = 1 and noting that D(1) = 0, we can calculate all derangements. For numbers up to 10, they turn out to be

D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44
D(6) = 265
D(7) = 1854
D(8) = 14833
D(9) = 133496
D(10) = 1334961

The math textbooks will also show another result that makes this even more beautiful.

The limit of (N!)/ D(N)  as  N  approaches infinity is the number
e (= 2.7182816576664037...).
This means, the answer to our probability question is very close to
1/e (= 0.367879464285714...).

I will be building on this in another problems soon.

UPDATE : See the solution to Partial Derangement which builds on this post.

Company Man

Book Review : Company Man
Author : Joseph Finder
My Rating : 4 out of 5 stars

This was the first book I read by Joseph Finder, who has written many best-sellers. And I was impressed.

The main character - Nick Conover - is CEO of Stratton, a huge manufacturer of office furniture, based in a small town in Michigan. He has recently fired thousands of employees and almost everyone in the town dislikes him. His house keeps getting broken into and he is receiving threats. To add to the stress, he has to raise his 2 kids (a young daughter, and a teenage son) all by himself, as his wife died in a car accident a year ago.

As the story opens, his family dog gets brutally murdered by the intruder, and during the next intrusion, Nick shoots the intruder and kills him. Instead of going to the police about it, he decides to hide it. Much more is written on the inside cover, but I will leave it there. And I would say, forget the inside cover, just read the book.

The books starts out slowly. Finder takes his time developing the characters, creating their lives in your mind. That's the real strength of the book. The interactions feel real. Their world feels real. Finder has done good research into how such a corporation would function on a day to day basis. It reminded me of Arthur Hailey.

Those strengths made me overlook the weaknesses. Our main guy Nick is not all that bright. Wonder how he became a CEO ! It takes him forever to see through the office politics. His judgment is quite poor. Maybe that's author's intention. The mystery itself and its inevitable conclusion is not that hard to guess. Still I found myself getting glued to the last part of the book, reading late into the night to finish it off.

I also have a problem about how long it took Finder to get into the rhythm. It was well past 300 pages when the book became truly gripping for me. Else I would have given this 5 stars.

I am very happy to have read this book and highly recommend it to mystery lovers

Juno

Movie Review : Juno

Director : Jason Reitman
Genre : Comedy
Released : December 2007
Starring : Ellen Page, Michael Cera, Jennifer Garner, Jason Bateman, Allison Janney, J.K. Simmons
My Rating : 8 out of 10

For some unknown reasons, I had simply missed out on watching Juno till now. It had all the buzz when Diablo Cody won the Oscar for Best Screenplay and the movie had a few other nominations. But then I just forgot about it. It was a mistake that I recently corrected.

The story opens when Juno (Ellen Page) - a teenager - discovers that she is pregnant. She chooses the route of adoption over abortion. Fortunately, she has supportive parents (Allison Janney, J.K. Simmons) and even finds the perfect couple (Jennifer Garner, Jason Bateman) desperately wanting to adopt her baby. We see these relationships progress till the story ends with the birth of the baby.

The marketing department for the movie has labeled this as a "comedy". I disagree with that label. Not because the movie is not funny. It certainly is. Although it's unlikely to generate any riotous laugh, but it will surely make you chuckle many times. The reason for my disagreement is, the movie is way more than a comedy. In Juno, what is not being said, is equally important.

Juno does have a tough external shell and is constantly bubbling with energy and quirky one-liners. But we also see her sensitive vulnerable side, and we completely understand what's going on in her mind, without she actually telling it all. That's true for all characters, even the ones that have very little screen time. It's amazing how Jason Reitman and Diablo Cody can paint a complete character with so few brushstrokes.

They are helped by superb performances all around. Juno may come across as a typical teenager initially, but Ellen Page shows us that she is also smart and courageous. Forced into adulthood, she is still learning about the world. Part girl, part woman, she is sometimes confused, even as she doesn't really want to admit it. Jennifer Garner is remarkable too. In general the female characters in this movie are stronger and more likable than the male characters.

The movie navigates around every melodramatic pothole but still clearly conveys the feelings. I would like to highlight the scene at the mall when Juno runs into Vanessa. There are surprising dialogues mixed in an emotional scene. That combination of sweet and tangy flavors is sprinkled all over the movie. And I would also urge you to listen to the songs that play in the background. The lyrics are amusingly offbeat, both musically and literally.

It's a short movie but still feels very complete. I highly recommend it.

Lexicographically Lowest Possible String

The qualification round for Facebook Hacker Cup happened last weekend. I was initially tricked by one of the problems. I thought I had solved it - but the next day while browsing some blogs about the problems,  my wife discovered a mistake I had made. Fortunately, I had solved the other problem correctly to qualify for the next round.

The problem appears simple enough. You have been given a set of string and you have to find a "lexicographically lowest possible concatenation" of these strings. An example makes it perfectly clear. Assume that the only characters in the strings are lowercase characters from 'a' to 'z'.

If the input is abc xyz pqr . The correct output should be abcpqrxyz .

Of all the possible ways in which you can concatenate the strings, this will be the first one if you arrange them in ascending order. Conceptually, this is equivalent to saying, find all the N! ways in which the strings can be combined, sort them in ascending order and output the first one.

That brute force approach is horribly inefficient. So the quick solution that comes to mind is, just sort all the strings in ascending order, and then iterate over them to concatenate them one after another. That will work with our example. That's what I did. So what's the issue ?

Problem with natural sort and concat 

Consider the following example case where the input is just these 2 strings[xa xab]
Since "xa" < "xab" a simple sort and append method will produce xaxab
This is not correct, as the other possible concatenation is the correct answer.
Because xabxa < xaxab

And that's the problem.

For any 2 strings S1 and S2, S1 < S2 does NOT imply (S1.S2) < (S2.S1).

This happens only if one string is a starting substring of another. There is NO problem with natural sort and concat in following cases.

For [abc pqrabc] the answer is still in natural order = abcpqrabc which is < pqrabcabc
For [abcd abczpqr]  the answer is still in natural order = abcdabczpqr which is < abczpqrabcd

Even when we have a starting substring, the simple natural sort and concat can be correct.

For [xa xaz] answer is still in natural order = xaxaz.

Correct solution

My new solution is still a sort and append. But when the strings are being sorted, simple comparison "if S1 < S2" should not be used. The correct comparison is "if (S1.S2) < (S2.S1)". So the strings should be placed in ascending order using the comparison of their concatenations.

Generally speaking, before concatenating the strings should be ordered
[S0 S1 S2 ... Sn]
such that
for any k, the concatenation (S[k-1].S[k]) < (S[k].S[k-1])

Then the entire concatenation would be lowest.

Informal Proof

That sounds intuitively correct. Still, since I was tricked once, I just want to make sure that this approach is indeed correct.

Let's say while sorting we decide to order the strings as [S1 S2] because (S1.S2) < (S2.S1). Then we check string S3, and since (S2.S3) < (S3.S2) we decide to put it last as [S1 S2 S3]. This will give us S1.S2.S3 as our answer. It's correct based on comparison of [S1 S2] and [S2 S3]. But what about the comparison of [S1 S3] ? How do we know that S3 should not be put ahead of S1 giving us the answer S3.S1.S2 ?

To prove that above ordring is indeed correct, we need to make sure that our comparison is transitively correct.

Prove that, if (S1.S2) < (S2.S1) and (S2.S3) < (S3.S2), then it implies (S1.S2) < (S3.S1)

The only interesting case in our ordered list [S0 S1 S2 ... Sn] is when the natural sorting order is violated for all 3 strings. Any ordering [S1 S2 S3] generated by our algorithm is trivially correct if S1 < S2. There is no point comparing S3 to S1 here. In fact we can simply combine such string pairs into one bigger string, and keep reducing the number of strings till we have a violation of the natural order in at least 3 successive strings.

Consider the natual sorting order [xa xab xabc]. But for us, the correct order is [xabc xab xa]. This is the only interesting case. We want to make sure our derived answer xabcxabxa is really the lowest.

Another example.

Consider the natual sorting order [xa xab xabz]. But for us, the correct order is [xab xabz xa]. This is NOT intersting as the order for first 2 strings [xab xabz] is just natural ordering. We can reduce this to [xabxabz xa] and now our solution is trivially correct.

To repeat, the natural sorting order of [S1 S2] will be violated only if entire S1 is a substring of S2, and (S2.S1) < (S1.S2).

So let's consider the case generally and name the substrings as X, Y and Z.

S1 = Z.Y.X

S2 = Z.Y

S3 = Z

Clearly S3 < S2 < S1 using natural order, but solution using our comparison came out to be in exactly the opposite order as [S1 S2 S3]. Let's prove it correct.

Also our algorithm decided that S2.S3 < S3.S2 - meaning Z.Y.Z < Z.Z.Y Removing identical substring from the beginignof both, gives us Y.Z < Z.Y and this implies Y < Z.

Now S3.S1 will be Z.Z.Y.X and compare this to S1.S2 which is Z.Y.X.Z.Y. Since we know that Z > Y, it follows that Z.Z > Z.Y. Therefore (S3.S1) is indeed > (S1.S2) and hence S3 should not be placed ahead of S1.

Maybe I made it too complicated. But I could not figure out a simpler proof. I can also prove it a bit more formally using induction, but I don't think it's simpler. In any case, the solution is really very simple to implement, and that's what matters !

The Alexander Cipher

Book Review : The Alexander Cipher
Author : Will Adams
My Rating : 3 out of 5 stars

I am always on the lookout for books by new authors. When I saw "Alexander Cipher" and read the description, I was very enthusiastic about reading it. Now, having read it, I am not so enthusiastic about recommending it.

The book calls itself thriller, and it's written in the style of a modern page turner. Problem is, there is not enough incentive to keep turning the pages. That's a shame, because there is definitely a lot of potential here. The idea is cool, the author can write a complex plot and develop characters if he chooses to. But by focusing more on the Hollywoodish presentation than substance, the author lets the potential remains just that - a potential. On the plus side, there are no major logical holes - at the end things are nicely tied together.

During a building construction (in Alexandria, Egypt) a necropolis gets discovered which leads to some clues about the real location of the sarcophagus of Alexander the Great. The excavation of this site and ensuing search for the location of Alexander's tomb entangles the lives of all characters in the story. The hero is Daniel Knox, an archeologist who is connected by just one degree of separation to everyone else in the story.

This is a decent idea, sort of Indiana Jones, sort of Da Vinci Code. And there is plenty of running around - in fact way too much running around. That doesn't leave author much scope to do anything else. There is a bit of history lesson, there is some character development (especially the Egyptians) - but there is no puzzle solving as was in Da Vinci Code. And since we are not invested in any of the characters, we really don't feel much for them, let alone root for them. As a result, the countless action scenes do not feel thrilling, as we really don't care about what happens to whom.

I am OK with mindless page turners, but not if they are this long. And this didn't have to be like that. Egypt, Alexander, lost tomb, treasure hunt with clues - this is more than enough ammunition to sprinkle a handful of historical trivia in a gripping thriller. Just stop making your characters run from a place to place every third page, escaping one danger after another and sit down to develop them, throw in some puzzles, blend in some more history, take the reader with you on an intelligent adventure ! Oh well.

I can neither recommend against reading this book, nor for it. Set your expectations right, and you may like it.

It's Complicated

Movie Review : It's Complicated
Director : Nancy Meyer
Genre : Comedy
Released : December 2009
Starring : Meryl Streep, Alec Baldwin, Steve Martin
My Rating : 6 out of 10

Nancy Meyer is known for light, comedy movies and "It's Complicated" is no exception. And .... hmmm, let's just say as it is - this is a "Chick Flick" just like her other movies.

But is it good ? The script starts out well, has some really funny moments. After about 3 quarters of it, the script forgets that it started out as a comedy, tries to change its genre to drama and makes "It's too complicated for itself". That's my attempt to make a pun on the name, just in case you missed.

Jane (Meryl Streep) is the owner of a bakery in an up-scale neighborhood. She is a divorcee, with 3 grown-up kids. She accidentally starts an affiar with her ex-husband (Alec Baldwin) who is currently married to a much younger woman. The romantic triangle is completed by Adam (Steve Martin) who is helping Jane build a dream kitchen.

It makes for an interesting and a bit novel set-up for a light-hearted comedy with a clear target audience demography. I have already stated what's problematic with the movie. Still it has numerous strengths to make it worth watching. The main strength, of course, is the perfect cast. Alec Baldwin does a nice job and we know exactly what type of person his character is. Steve Martin, as a bit of surprise, plays a serious, sensitive and reserved person. The center of the movie is naturally the Godess of Acting herself - Merryl Streep.

The movie is less than 2 hours, but could have been even shorter. It is definitely enjoyable. There are more than a few adult only jokes in it, else it could have been OK for kids. In any case, I really doubt if there are any kids (of any age) interested in watching romance between old folks ! Just watch it for Merryl Streep, if for no other reason.