puzzle: N persons sitting on round table. No of ways of handshakes without crossing any other handshakes

algorithm puzzle catalan
user2328404 picture user2328404 · Aug 6, 2013 · Viewed 10.8k times · Source

We have n persons sitting on a round table. Any person can do a handshake with any other person. In how many ways these n people can make handshakes so that no two handshakes crosses each other.

I found this puzzle in a technical interview forum, but no answer. One way i could think of was find all the permutations of handshakes and then check each permutation whether it satisfies or not.

Can anyone please sugget any other solution which is more efficient.

@edit: Clarification from comments: N would be even.

Answer

Buhb picture Buhb · Aug 6, 2013

I would try a divide and conquer solution. if person 1 shakes hand with person x, it splits the rest of the people into two groups, that can be treated as sitting at two round tables.

Related questions

How to print all possible balanced parentheses for an expression?

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses): (((ab)c)d), ((…

Read More
How to find list of possible words from a letter matrix [Boggle Solver]

Lately I have been playing a game on my iPhone called Scramble. Some of you may know this game as Boggle. Essentially, when the game starts you get a matrix of letters like so: F X I E A M …

Read More
Expand a random range from 1–5 to 1–7

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7. What is a simple solution? What is an effective solution to reduce memory usage or run …

Read More