Mathematicians... I need help :) (1 Viewer)

[MichaelPe]

I'm trying to get some more information about a problem I'm trying to solve, and I figured that this would be the best place to ask.

Basically, assume that we have N people and we would like them to pair up and talk for a few minutes. After a few minutes, I'd like them to swap partners and talk with someone new. And, this cycle continues until everyone has talked with everyone else, never speaking to the same person twice.

So, let's take the case of 6 people:

Round 1: (1,2) (3,4) (5,6)
Round 2: (1,3) (2,5) (4,6)
Round 3: (1,4) (2,6) (3,5)
Round 4: (1,5) (2,4) (3,6)
Round 5: (1,6) (2,3) (4,5)

In 5 rounds, everyone has had the chance to talk with everyone exactly once.

I solved the previous example by hand (trial-and-error), but I'm wondering if there is an algorithm to solve this problem for the general case of N people. I understand that the number of people must be even for this to work, and that we must evaluate each pairwise permutation (N-choose-2). Also, for this to work optimally, the total number of pairwise permutations must be perfectly divisible by the number of pairs at a time (N/2). In other words, the above case of 6 people worked out because there were 15 pairwise permutations and 3 pairs at a time, hence 5 rounds.

This should work for other values, such as 8, 10, 12, 14, 16: yielding 7, 9, 11, 13, 15 rounds respectively. So, does this algorithm exist? Does it have a name?

Thanks in advance!

 

[Paul_Sjordal]

It will always be (N-1) rounds. If you have N people, then each person has N-1 other people to talk to (1 + N-1 = N). Not too complicated.

 

[MichaelPe]

I realize that there will always be N-1 rounds, but that wasn't my question. Essentially, I'm asking if there is a way to determine the pairs at each round.

For example, when we have 6 people, the 15 pairwise permutations are:

1. (1,2)
2. (1,3)
3. (1,4)
4. (1,5)
5. (1,6)
6. (2,3)
7. (2,4)
8. (2,5)
9. (2,6)
10. (3,4)
11. (3,5)
12. (3,6)
13. (4,5)
14. (4,6)
15. (5,6)[/list=1]
    So, is there an algorithm that determines which 3 pairs occur in each round? In this example, it's fairly simple to do it using trial-and-error, but I'm looking for a general method which will let me do it for N=16 or greater. Obviously, this algorithm is applicable to many domains such as peer-to-peer packet sending, job-shop scheduling tasks, etc...

 

[MichaelPe]

Also, perhaps I should give a negative example where the scenario may fail... just so that it's clear that the algorithm I'm looking for must produce an optimal solution:

Again for the case where N=6:
Round 1: (1,4) (2,5) (3,6)
Round 2: (1,5) (2,6) (3,4)
Round 3: (1,6) (2,4) (3,5)
Round 4: (1,2) (4,5) FAIL! (3,6)
Round 5: (1,3) (4,6) FAIL! (2,5)
Round 6: (2,3) (5,6) FAIL! (1,4)

As you can see, this scenario fails after 3 rounds because it is no longer possible to have 3 concurrent pairs at each round, and hence - a 6th round is required. Thus, an inferior solution results in many wasted cycles and idle waiting time.

 

[Paul_Sjordal]

In that case, you're looking at a mess of nested iterative loops with inelegant if-then statements to catch previously occurring combinations. I don't think there's a nice, pat, elegant solution like you're looking for.

 

[Jeff Gatie]

Never mind, read the problem wrong!

 

[Denward]

My intuition tells me that there is an elegant algorithm, but I haven't been able to figure it out in the 15 minutes I spent thinking about it.

Jeff, your C code only gives you all the combinations, but Michael wants to know how you can group them into N-1 rounds.

 

[MichaelPe]

Thanks all for trying... I appreciate it. Actually, I've gotten very close to developing a working algorithm, so I'll share it once I finish it.

 

[Greg_R]

In terms of computing, I think this algorithm would be efficient:

1) Divide the N players into 2 equal groups, 0 to (N/2-1) and N/2 to N. Let's call the two new groups A and B.
2) Match (A0-B0), (A1-B1), (A2-B2), etc.
3) rotate the B position by one, yielding (A0-B1), (A1-B2), etc. Rotate N/2 - 1 times (so A0 will have talked to every member in the B group). Think of it as an inner and outer circle of groups (with the outer one rotating).
4) Take the A and B groups and repeat #1-#3 (seperately). This solution lends itself to recursion rather nicely.

Total compute time would be N/2 + (2*(N/4)) + (4*(N/8)) + ... which I belive converges to (N/2)log2(N)

edit: oops! The total number of matches should be:
C(N 2) (where C = combinatorial)

In parallel it would be N-1...

 

[Paul_Sjordal]

Alright, I admit I didn't read your post all that carefully, but wouldn't your algorithm miss an awful lot of combinations? E.g. A-B, 1-2, etc.

 

[Greg_R]

Not sure if you're referring to me but...

Let's take a case of 8 participants.

----- group 8->5, 4->1 & match (note the simple decending counter for the B position, A stays constant)
Round 1a: (8-4),(7-3),(6-2),(5-1)
Round 1b: (8-3),(7-2),(6-1),(5-4)
Round 1c: (8-2),(7-1),(6-4),(5-3)
Round 1d: (8-1),(7-4),(6-3),(5-2)
----- split 8->5 into 8->7 and 6->5
Round 2a: (8-6),(7-5)
Round 2b: (8-5),(7-6)
----- split 4->1 into 4->3 and 2->1
Round 3a: (4-2),(3-1)
Round 3b: (4-1),(3-2)
----- Since each group size = 2, do the final matching
Round 4a: (8-7)
Round 4a: (6-5)
Round 4a: (4-3)
Round 4a: (2-1)


C(8 2) = 28 matches

 

[MichaelPe]

Greg,
Thanks. I had considered that solution, but unfortunately it only works for N=2^m (in other words, N=2,4,8,16,32,etc).

The solution I'm working on now is different from the one you suggested, but it seems to produce identical results for N=8. Obviously, a "divide and conquer" approach won't work for the general case (in which N isn't a power of 2) because that will yield a non-optimal solution involving "waiting time".

 

[Denward]

Here is someone's research paper on a similar topic.
http://www.info.univ-angers.fr/pub/h...s/ECAI00WS.pdf

The paper describes the problem on page 2 and it is identical to yours except for one big thing. The context of the problem is a sports league of N teams and they want a single round robin schedule completed in N-1 days with each team playing once per day. Each day therefore has N/2 games. There's only one gym so there are N/2 "scheduling slots" each day. The big difference is the paper's additional constraint that no team play more than twice in a particular scheduling slot over the course of the season.

I don't know what your math background is or whether you can follow the notation. If you look at the chart on page 9, the proposed method called TS-SLSP doesn't do very well once N>24.

Michael, if you're really serious about solving this problem, perhaps some of the references in this paper can guide you to an answer where you don't have the scheduling slot constraint.

 

[Denward]

One way to think of your problem is to construct it as a NxN symmetric matrix. Let's denote the matrix as M.

The value of M(i,j) represents the round in which person i meets person j. The matrix must be symmetric since M(i,j) must equal M(j,i) for all values of i and j. Furthermore M(i,i) must be zero for all values of i since a person can't meet with himself.

So the problem becomes a question of filling the matrix such that each row and each column has the numbers 0,1,2,...N-1 in it.

If you think of it this way, it can be described as an "integer programming" problem. When I studied integer programming algorithms 20 years ago, they were essentially trial and error iterations. The goal of a researcher was to determine more efficient ways to iterate until a feasible solution was found. I'm sure a solution to your problem exists as this sounds like a classic classroom problem. You could find a textbook on integer programming and see what the latest methods are.

 

[MichaelPe]

Wow... thank you so much, Denward. This is exactly what I was looking for!

I decided to take your advice and check up some references on "round robin tournament scheduling" and found various approaches - many of which were similar to the algorithm I was working on. Oh well... no need to reinvent the wheel, right?

Here's a page with lots of great resources, including source code, applets, tables, edge graphs, and tournament grids:
http://www.devenezia.com/downloads/round-robin/

And, thanks again to everyone for your much appreciated help!

 

[Denward]

Nice site, Michael. I especially like the edge graphs. Notice the pretty patterns when N=2^x. Then see how confusing everything gets when N is not a power of 2.

 

[Paul_Sjordal]

no need to reinvent the wheel, right?

There is never a need to do that, and in fact it is generally an amazingly stupid thing to do, but let's be perfectly honest: we all do it from time to time. Usually because you simply didn't know someone had already done it or you didn't know how to find it. PS—my version of DELTREE was faster than the one that shipped with DOS. *sniff*

 

[MichaelPe]

PS—my version of DELTREE was faster than the one that shipped with DOS. *sniff*

Hehe... that's great! Then again, why am I not surprised that MS code isn't optimized.

 

[Denward]

Michael,
I was looking at that site again and I noticed that they had 2 sets of graphs for 2 different methods. When you pick Edge Graphs from the home page, you get the First Fit graphs. At the top of the graphs page, you can also choose the Cyclic graphs. These Cyclic patterns are much more intuitive for any value of N.

I found that interesting. Maybe you don't.

 

[MichaelPe]

Denward,
Yes, I had noticed that (see my previous post)... and it is a lot more intuitive - not to mention it's much simpler to code.