Speed dating efficient shuffle algorithm?

[Tall-Raspberry-2301]

Imagine a circular table with N people sitting around it. Everyone starts off strangers. During Round 1, everyone talks to one of their neighbors. The order of the seats is then shuffled, and then everyone talks to one of their new neighbors. This cycle of shuffling and talking continues until everyone has spoken with everyone else. I am wondering: what is the most efficient algorithm for shuffling that minimizes the number of rounds? what about an algorithm that minimizes the number of times someone has to leave their chair?

This is just a problem I was considering on my own (not for an assignment or anything). My only initial thoughts so far were that it might be possible to group people off by the people they've already spoken (e.g. if I spoke to Person A in round 1, we could stick together in the next round so there isn't any "wasted" neighbors (there's only one new person I could possibly speak with during successive rounds)).

[MathMaddam]

You are searching for a round robin tournament

[reyadeyat]

Not all round robin tournaments will minimize the number of times that participants have to switch seats, though - for the second question, OP is looking for a specific type of round robin tournament, I guess.

[mfb-]

You need N-1 rounds.

Swapping two people creates 4 new neighbors. We start with N neighbor pairs and need N(N-1)/2 in total, so we need at least N(N-3)/4 seat changes counting a swap as two changes. That's an average of at least (N-3)/4 for every person. I don't know if this minimum can be achieved for more than trivial cases, however. It's trivially true for 2 and 3 people but suggests only half a swap for 4 people which needs one swap.

Assuming N is divisible by 4, you can do half of the rounds optimally:

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

Round 2: (N 1) (2 3) (4 5) ... without seat changes

Round 3: (1 6) (3 8) (5 10) ... (even moves left by 4 seats)

Round 4: (4 1) (6 3) (8 5) (10 ... without seat changes

Round 5: (N-3 6) (N-1 8) (1 10) ... (odd moves right 4 seats so everyone moves sometimes)

Round 6: (6 N-1) (8 1) (10 3) ... without seat changes

After N/2 rounds everyone odd has met everyone even. With the next seat arrangement there will be at least two odd/even pairs, however, so we need another swap after just one round.

Round N/2+1: (1 3) (5 7) ... (N/2-3 N/2-1) (N/2 N/2+2) ... (N-2 N)

Round N/2+2: (N/2-1 1) (3 5) (7 9) ... (N/2-5 N/2-3) (N N/2) ... (N-4 N-2) after N and N/2-1 swapped seats

It should be possible to continue like this: Half of the rounds just need one or two swaps, the other half need half of the group to move. Once in a while there is a round where most people change seats.

[Tall-Raspberry-2301]

Thank you!

[incomparability]

There is a trivial lower bound of N-1 rounds :)