CODEWITHSUNDEEP
algorithmdata-structures
Jackson Tale
Jackson Tale

Reputation: 25812

What's the grouping plan so that every two people are grouped together just once?

So, we have N people.

Everyday, we make N/2 groups out of them, i.e., 2 people are in one group.

We keep grouping everyday, until every two people have been paired exactly once, no more no less.

Please give the grouping plan for every day.

Here are my thoughts:

Out of N people, there are N * (N-1) / 2 possible pairs. Since everyday we will have N/2 pairs, totally we will need N-1 days.

So basically, if our algorithm takes a list of N people as input, we will output N-1 lists, each list will contain the pairs for a day.

But how to organise these N * (N-1) / 2 pairs into N-1 days?

I know how to do it in a bruteforce way, like worst case, we try every combinations of pairs for every day, or better use hashtset to see whether a combination for a day is possible or not (a hashset for a day).

But I think there must be a more elegant and efficient way to solve the problem. Graph?

Upvotes: 1

Views: 172

Answers (1)

mcdowella
mcdowella

Reputation: 19601

Have a look at http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm - This seems to answer your question. I have also seen this discussed in the context of chess matches and bond settlements.

Upvotes: 1

Related Questions