[Guest]

It sounds simple: I have n people in a room, each of whom must have a 1 minute conversation with every other person. Each pair sits at a table to have the conversation, then moves on, kinda like speed-dating. What algorith do I use to schedule them?

For example, if I have 4 people (n=4), labelled A,B,C,D, I know each person will require a 2-way conversation with 3 others, making a total of 6 conversations. Since the conversations will take place 2 at a time (4 people in pairs), it means there will be 3 sessions, and the whole process will take 3 minutes.

Scheduling this by trial and error, I get this result, which is fine:

. . . . . . . .. . . . .Table 1. . . . . . Table 2

Session 1 . . . . . A-B. . .. . . . . . . .C-D

Session 2. . . . . .A-C. . . . . . . . . . B-D

Session 3. . .. . . A-D. . . . . . . . . . B-C

So although I can do it by trial and error with low values of n, I have yet to discover a generalised method of scheduling. My first real-world version is with 20 people (10 tables, with 19 sessions each). Any help would be appreciated!

Edited December 1, 2011 by Sword

[curr3nt]

Are you trying to get the minimal duration required to hold the sessions or the actual scheduling detail?

[Prof. Templeton]

Sounds like a hand shaking problem.

[Guest]

i think permutations and combination can be used for general solution but i've not read that topic yet

[CaptainEd]

arrange the tables from, let's say, East to West, arrange the people at the tables, sitting North and South.

After one minute, each person in both lines moves to his/her right. The person moving off one end or the other moves to the other side of the same table.

Once 20 sessions have happened, rotate the North people by one spot, the Westmost person rotating to the Eastmost position on the North side.

Now, do 20 more sessions, rotating everybody as before.

You are done. Nobody saw anybody twice, nobody missed anybody.

[CaptainEd]

arrange the people as described--20 people at 10 tables.

Chat

9 x (Rotate the entire ring, Chat)

Rotate the North ring

Chat

8 x (Rotate the entire ring, Chat)

[CaptainEd]

No, it's not that easy. The first half of my algorithm correctly matches each odd person with each even person. The second half matches people with some they've already seen and therefore missing some as well. Back to the drawing board.

[Prof. Templeton]

No, it's not that easy. The first half of my algorithm correctly matches each odd person with each even person. The second half matches people with some they've already seen and therefore missing some as well. Back to the drawing board.

Well the math is easy

n(n-1)/2 would be the number of total sessions.

The scheduling is more difficult but you could probably force a schedule after a bit.

[CaptainEd]

I've got a schedule that wastes one sitting, but is totally easy to create, for any N people. But right this minute, I can't create a spoiler...I'll keep trying.

[CaptainEd]

You have an East-West line of 10 tables, with 20 people at the North and South sides of the tables, and add a side chair with a ghost (either an empty space, a moderator, a pumpkin, etc.)

* Chat

* 19 x (Rotate the entire ring including the ghost; Chat)

Each person has spoken to each other person and has faced the Ghost once. Each person has sat out in the side chair once.

There are 20 sittings, while I admit you could have done the job in 19 sittings with a lot more calculation...

This algorithm works optimally if there's an odd number of people.

)

[Prof. Templeton]

Here's a schedule I found

[ 1 2 | 3 4 | 5 6 | 7 8 | 9 10 | 11 12 | 13 14 | 15 16 | 17 18 | 19 20 ]

[ 1 3 | 2 4 | 5 7 | 6 8 | 9 11 | 10 12 | 13 15 | 14 16 | 17 19 | 18 20 ]

[ 1 4 | 2 3 | 5 8 | 6 7 | 9 12 | 10 11 | 13 16 | 14 15 | 17 20 | 18 19 ]

[ 1 5 | 2 6 | 3 7 | 4 8 | 9 13 | 10 14 | 11 17 | 12 18 | 15 19 | 16 20 ]

[ 1 6 | 2 5 | 3 8 | 4 7 | 9 14 | 10 13 | 11 18 | 12 17 | 15 20 | 16 19 ]

[ 1 7 | 2 8 | 3 5 | 4 6 | 9 19 | 10 20 | 11 13 | 12 14 | 15 17 | 16 18 ]

[ 1 8 | 2 7 | 3 6 | 4 5 | 9 20 | 10 19 | 11 14 | 12 13 | 15 18 | 16 17 ]

[ 1 9 | 2 10 | 3 11 | 4 12 | 5 15 | 6 16 | 7 17 | 8 18 | 13 19 | 14 20 ]

[ 1 10 | 2 9 | 3 12 | 4 11 | 5 16 | 6 15 | 7 18 | 8 17 | 13 20 | 14 19 ]

[ 1 11 | 2 12 | 3 9 | 4 10 | 5 19 | 6 20 | 7 15 | 8 16 | 13 17 | 14 18 ]

[ 1 12 | 2 11 | 3 10 | 4 9 | 5 20 | 6 19 | 7 16 | 8 15 | 13 18 | 14 17 ]

[ 1 13 | 2 14 | 3 17 | 4 18 | 5 9 | 6 10 | 7 19 | 8 20 | 11 15 | 12 16 ]

[ 1 14 | 2 13 | 3 18 | 4 17 | 5 10 | 6 9 | 7 20 | 8 19 | 11 16 | 12 15 ]

[ 1 15 | 2 16 | 3 13 | 4 14 | 5 17 | 6 18 | 7 9 | 8 10 | 11 19 | 12 20 ]

[ 1 16 | 2 15 | 3 14 | 4 13 | 5 18 | 6 17 | 7 10 | 8 9 | 11 20 | 12 19 ]

[ 1 19 | 2 20 | 3 15 | 4 16 | 5 11 | 6 12 | 7 13 | 8 14 | 9 17 | 10 18 ]

[ 1 20 | 2 19 | 3 16 | 4 15 | 5 12 | 6 11 | 7 14 | 8 13 | 9 18 | 10 17 ]

[ 1 17 | 2 18 | 3 19 | 4 20 | 5 13 | 6 14 | 7 11 | 8 12 | 9 15 | 10 16 ]

[ 1 18 | 2 17 | 3 20 | 4 19 | 5 14 | 6 13 | 7 12 | 8 11 | 9 16 | 10 15 ]

[Guest]

I agree with above but if n is a power of 2 you can do it without wasting any time, otherwise i think you have to waste time somewhere

number all 1-n, even numbers face all odd numbers, then number all odd numbers 1- n/2, those evens face those odds at the same time do the same with the other odds etc.

[curr3nt]

It can be done in 19 sittings...we just need a system for dealing with odd number sets.

n = 16

Pairing is top and bottom

ABCDEFGH

IJKLMNOP


Since n/2 is even use the shift.

Shift the lower row for 8 sittings.  Pairing A-J with each K-T.


If n/4 was even the next step would be split the set in half and swap the bottom row with the other top and repeat for n/(2 * ( i + 1 )) where i is each iteration.


ABCD  IJKL

EFGH  MNOP


Shift for 4 sittings


Then


AB  EF  IJ  MN

CD  GH  KL  OP


Shift for 2 sittings


And finally


A  C ... M  O

B  D ... N  P


Making 8 + 4 + 2 + 1 = 15 sittings

n = 20

The first n/2 sittings work since 10 is even.


The problem arrives when they are split into two sets of 5.


Just have a start to my thinking...


Say m is the odd value of n/(2* ( i + 1 ))


Start with m-1 basic shifts so in our case 4 (for my sanity I'm starting with one shift already done so that the unused shift is AF BG CH DI and EJ


ABCDE ABCDE ABCDE ABCDE

GHIJF HIJFG IJFGH JFGHI


Then m sets each using one piece of the unused set


A BC GH

F DE IJ


B AC FH

G ED JI


C AD FI

H BE GJ


D AB FG

I CE HJ


E AB FG

J DC IH


Haven't worked out a better way to generalize it yet.

[CaptainEd]

 

OK, this is cute. 

Remember the odd number n, where you have an extra ghost 

who rotates around with everybody? 

Now, with any number 2n, we'll have one person who is a fixed point. 

Place n tables in a row, West to East, 

with seats at N and S sides of each table. 


Number the seats clockwise starting with the NW seat. 

So the North seats are 1...n, and the South seats are n+1...2n 


The person in seat n+1 remains stationary throughout the entire process. 

Rotation consists of each person (except the stationary one) 

moving to the next higher numbered seat, 

wrapping around from the Southwest seat to the Northwest seat. 


Example: in the case n=5, using curr3nt's A-Z labelling of the people: 


ABCDE 

JIHGF 


JABCD 

IHGEF 


IJABC 

GHEDF 


GIJAB 

HEDCF 


HGIJA 

EDCBF 


EGHIJ 

DCBAF 


DEGHI 

CBAJF 


CDEGH 

BAJIF 


BCDEG 

AJIHF 

Edited December 1, 2011 by CaptainEd

[Guest]

*edit* I spent a long time fiddling with the table, and in the meantime, there were a lot more replies. So I suspect it's been cracked in the meantime!

Thank you, Captain Ed - that is very promising. I tried the method (as I understand it) to n=6, which should require 5 sessions of 3 tables.

I used a moderator M as an extra.

Here's what I got, attached as a PDF as I could not for the life of me get the table to display here!:

It seems to work, but as you say, it requires extra sessions - in this case it requires 7 sessions instead of 5. Each person gets to converse with each other person only once, but also gets to sit on the naughty chair on their own for one session. Furthermore each person, apart from one, gets to have a wasted chat with the moderator.

For an odd number of people, I think this is a perfect solution- the extra seat is just taken up by each person in turn, and there is no way to avoid this, given that you can't divide an odd number into pairs.

I am waiting in anticpation for your more general solution for any n, or an optimal solution for any even number n!

Many thanks again - that has been most enlightening.

Rgds,

Michael.

Document3.pdf

Edited December 1, 2011 by Sword

[curr3nt]

Good find CaptianEd!

[Guest]

OK, this is cute.

Remember the odd number n, where you have an extra ghost

who rotates around with everybody?

Now, with any number 2n, we'll have one person who is a fixed point.

Place n tables in a row, West to East,

with seats at N and S sides of each table.


Number the seats clockwise starting with the NW seat.

So the North seats are 1...n, and the South seats are n+1...2n


The person in seat n+1 remains stationary throughout the entire process.

Rotation consists of each person (except the stationary one)

moving to the next higher numbered seat,

wrapping around from the Southwest seat to the Northwest seat.


Example: in the case n=5, using curr3nt's A-Z labelling of the people:


ABCDE

JIHGF


JABCD

IHGEF


IJABC

GHEDF


GIJAB

HEDCF


HGIJA

EDCBF


EGHIJ

DCBAF


DEGHI

CBAJF


CDEGH

BAJIF


BCDEG

AJIHF 

Bingo! You've done it, sir! Much obliged for all the replies - I hope you at least enjoyed the bit of challenge, since all I can really do in return is buy you a virtual beer. Cheers!

[curr3nt]

If n is even

	m = n/2

	if m is even

		create m pairings and shift the lower set

Example: n = 8; m = 4

ABCD ABCD ABCD ABCD

EFGH FGHE GHEF HEFG

		Switch top right m/2 people with bottom left m/2 with each other and run both sets through with n = m

Example:  Run each of the following from the top as separate but concurrent sessions

AB EF

CD GH


	if m is odd

		create m pairings, fix the bottom right peron and rotate everyone else

Example: n = 6; m = 3

ABC EAB DEA CDE BCD

EDF DCF CBF BAF AEF


if n is odd

	m = int(n/2)

	create m settings with each person sitting out one and rotate

Example: n = 5

ABC EAB DEA CDE BCD

ED  DC  CB  BA  AE

Does that cover it all?

Edited December 1, 2011 by curr3nt

[CaptainEd]

If n is even

	m = n/2		(regardless of whether m is even)

        create m pairings, fix the bottom left person and rotate everyone else

Example: n = 8; m = 4

ABCD GABC FGAB EFGA DEFG CDEF BCDE

HGFE HFED HEDC HDCB HCBA HBAG HAGF


if n is odd

	m = int(n/2)

	create m settings with each person sitting out one and rotate

Example: n = 5

ABC EAB DEA CDE BCD

ED  DC  CB  BA  AE

Does that cover it all?

Yes, but I've simplified the even cases above. Also moved the fixed point to the SouthWest side.

[CaptainEd]

...I hope you at least enjoyed the bit of challenge, since all I can really do in return is buy you a virtual beer. Cheers!

And thank you, Sword. It was indeed an interesting challenge. As you see, it took us a bunch of tries to figure it out. I'd really like to know how Prof Templeton found his schedule. I can't keep track of 20 items myself...

[Prof. Templeton]

And thank you, Sword. It was indeed an interesting challenge. As you see, it took us a bunch of tries to figure it out. I'd really like to know how Prof Templeton found his schedule. I can't keep track of 20 items myself...

Twas on the internet, of course. If you study it, there is an elegant pattern contained within.

[Peekay]

Consider the 20 people in a ring pulled tight at two ends. So, you have 2 rows of 10 people each (1 facing 20, 2 facing 19, etc.)

Next, you rotate the ring once (say clockwise). So, 20 moves onto the top row and faces 19, 1 faces 18, etc.

Continue this operation 19 times. Every person meets everyone else once and you have the schedule.

For an odd number of people, you will have to add the "dummy" one to pair them off.

[Guest]

I found this wikipedia article - http://en.wikipedia.org/wiki/Round-robin_tournament , which describes the problem and the solution elegantly. Captain Ed and others had it pretty much perfect.

Assign each participant a letter of the alphabet and pair them off. Choose one participant, who stays stationary throughout, and then for each session, rotate the other players one position (either always clockwise or always anticlockwise).Keep going until the ring is almost back in its initial position. The solution for n=odd and n=even is identical, except that for n=odd we add a dummy to make it even. (If there is a dummy, he could be chosen to be stationary, but need not be

[Guest]

Twas on the internet, of course.

Really?