Sunday, August 17, 2014

Math by brute force

I came across a problem in a book on Combinatorics

In how many ways can 5 gentleman and 3 ladies be seated such that no two ladies sit next to each other?

The book's answer was 5!. Clearly not very believable, I decided to warm myself up and try and find an answer.

My first answer was

8! - 2.7! - 6.6!

Something did not seem right, so I decided to use brute force. I wrote quick python code to list 8! permutations (all of them) and discard positions with two ladies together (yes, I permuted classes with numbers and types). The answer was 14400. Clearly I missed something and the computer cannot be wrong - well brute force is usually slow but right :)

A little more thought and use of common sense got me to the right answer

8! - (3 C 2)*2*7! + 6.6! (via inclusion/exclusion principle)

I am so excited to use brute force to check my answers - do you?




Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...