1

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?

Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

1 Answers1

1

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.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • Rather than just providing a link, [it would be preferable](http://meta.stackexchange.com/q/8259) to include the essential parts of the answer here, and just provide the link for additional reference. If you're not up to this task, you should consider simply leaving a comment on the question instead of posting an answer. – Bernhard Barker Dec 01 '13 at 18:25