Mathematicians... I need help :)

Discussion in 'After Hours Lounge (Off Topic)' started by MichaelPe, Oct 27, 2003.

  1. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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! [​IMG]
     
  2. Paul_Sjordal

    Paul_Sjordal Supporting Actor

    Joined:
    May 29, 2003
    Messages:
    831
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  3. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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...
     
  4. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  5. Paul_Sjordal

    Paul_Sjordal Supporting Actor

    Joined:
    May 29, 2003
    Messages:
    831
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  6. Jeff Gatie

    Jeff Gatie Lead Actor

    Joined:
    Aug 19, 2002
    Messages:
    6,531
    Likes Received:
    15
    Trophy Points:
    0
    Never mind, read the problem wrong!
     
  7. Denward

    Denward Supporting Actor

    Joined:
    Feb 26, 2001
    Messages:
    552
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  8. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  9. Greg_R

    Greg_R Screenwriter

    Joined:
    Apr 9, 2000
    Messages:
    1,996
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    Portland, OR
    Real Name:
    Greg
    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...
     
  10. Paul_Sjordal

    Paul_Sjordal Supporting Actor

    Joined:
    May 29, 2003
    Messages:
    831
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  11. Greg_R

    Greg_R Screenwriter

    Joined:
    Apr 9, 2000
    Messages:
    1,996
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    Portland, OR
    Real Name:
    Greg
    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
     
  12. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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".
     
  13. Denward

    Denward Supporting Actor

    Joined:
    Feb 26, 2001
    Messages:
    552
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  14. Denward

    Denward Supporting Actor

    Joined:
    Feb 26, 2001
    Messages:
    552
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  15. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    Wow... thank you so much, Denward. This is exactly what I was looking for! [​IMG]

    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? [​IMG]

    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! [​IMG]
     
  16. Denward

    Denward Supporting Actor

    Joined:
    Feb 26, 2001
    Messages:
    552
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  17. Paul_Sjordal

    Paul_Sjordal Supporting Actor

    Joined:
    May 29, 2003
    Messages:
    831
    Likes Received:
    0
    Trophy Points:
    0
     
  18. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
     
  19. Denward

    Denward Supporting Actor

    Joined:
    Feb 26, 2001
    Messages:
    552
    Likes Received:
    0
    Trophy Points:
    0
    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.[​IMG]
     
  20. MichaelPe

    MichaelPe Screenwriter

    Joined:
    Feb 22, 1999
    Messages:
    1,115
    Likes Received:
    0
    Trophy Points:
    0
    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. [​IMG]
     

Share This Page