Algorithm or not

[Julmasara]

I have a variable amount of participants.
Each participant needs to talk to another participant in a MINIMAL AMOUNT OF TOTAL ROUNDS.

Currently my application generates:
R1____R2____R3____R4____R5___R6____R7
P2-P1,P3-P1,P4-P1,P5-P1,P6-P1,P5-P3,P6-P3
P4-P3,P4-P2,P3-P2,P6-P2,P5-P2,P6-P4,P5-P4
P6-P5

Though, it can be doen in 5 rounds (manually generated):
R1____R2____R3____R4____R5___R6____R7
P2-P1,P5-P1,P3-P1,P4-P1,P1-P6,-----,-----
P4-P3,P4-P2,P5-P2,P2-P6,P2-P3,-----,-----
P6-P5,P3-P6,P4-P6,P3-P5,P4-P5,-----,-----

(Rx = Round, Px = Participant)


It's quite easy to build a list ofunique combinations of participant-pairs and arrange them over each round.

But how do I continue?. Because of my lack of knowledge I can't seem to solve this puzzle.
Do I need some sort of algorithm for this? If so, can you point me in the right direction?

Bonus:
Of all the tables (2 seats per table) there's 1 with a digital camera, which records the conversation (educational purposes).
Every participant must be placed (at least once) at the camera-table.

[Zachm]

You can deal with each participant by itself, something like this:

1. For each round r, keep a list of pairs assigned to round r, lets call this list Pairs(r).

2. When algorithm starts, all the lists are empty, but you already know that if there are N participants, you only need N-1 rounds to cover all pairs, hence N-1 lists.

3. In addition keep a list of all unique pairs, AllPairs, and initialize it
with all unique pairs (order of participants inside a pair must not matter).

4. Algorithm pseudo code goes something like:
For each participant p do
{
For each round r , do
{
If p is not part of any pair in Pairs(r) Then
For each participant q (q!=p), do
{
If q is not part of any pair in Pairs(r) AND
the pair (p,q) is in AllPairs Then
{
1. Insert the pair (p,q) to Pairs(r).
2. Remove the pair (p,q) from AllPairs.
}
}
}
}

As for the bonus - make the "special table" the 1st one in the list of pairs for each round and you will get this requirement.

Regards,
Zachm

[Julmasara]

I've attached a screenshot of my application's datagrid, taken after the round-participant arrangement ran.

The result is based on the following/your logic


foreach participant p1
{
for each round
{
foreach participant p2 != p1
{
if(
p2 not in current round
p1 not in current round
p2 and p1 have not paired yet)
then -> make unique pair and assign it to current round.
}
}
}

As you can see, I still end up with the situation that certain participants have to wait a round or two.
(round 6 and 7 are not in the grid because of the round limitation I've set in the code.)

Thanks alot for sharing your thoughts on this.
Very much appreciated!!

P.S. Deelnemer = Participant, RondeX = RoundX

[Zachm]

Looking at your table again, I just realized that the solution is much more trivial (and that my initial solution is wrong :( )

Participant R1 R2 R3 R4 R5

P1 P2 P3 P4 P5 P6

P2 P3 P4 P5 P6 P1

P3 P4 P5 P6 P1 P2

P4 P5 P6 P1 P2 P3

P5 P6 P1 P2 P3 P4

P6 P1 P2 P3 P4 P5


Notice that if you take the sequence P1-P6 and rotate it one time each round, you'll get the matching you need for each of the participant.

In round one, the sequence P1 - P6 is rotated once to the left - the sequence goes:
P2-P3-P4-P5-P6-P1.

In round two, the sequence P1 - P6 is rotated twice to the left - the sequence goes:
P3-P4-P5-P6-P2-P1.

And so on.

I think it's quite easy to fill a "magic square" matrix like this.
Only seeing your output made realize how easy it really is :)....

Regards,
Zachm

[Julmasara]

This won't work either.
According to your schema:
P1 meets P2 in round 1, but P2 is meeting P3 as well in that round... and so on.

I've asked my question on another forum and a member'sproposed solution seems to work. However, currently I'm walking into other issues.

If you want to contribute to, or follow the thread:
http://www.codeproject.com/script/Forums/View.aspx?fid=326859&msg=2757023

Thanks for your effort to help me out!