2
$\begingroup$

Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people.

I'm in a team and I want to plan the ideal speedback setup: all team members have to give feedback to eachother. I want to group people in a way that maximizes the concurrency of simultaneous pairs so we reduce the total time of the sessions.

Consider the input: "alexandre", "sergiu", "joana", "tiago", "susana", "david"

combinations(6,2) = 15 possible pairs

1st session:

"alexandre" with "sergiu"
"joana" with "tiago"
"susana" with "david"

2nd session:

"alexandre" with "joana"
"sergiu" with "tiago"
"joana" with "david"

3rd session:

...

you get the ideia.. until everyone "dates" everyone.

I need all the possible pairs to be matched in the end.

Do you how to get this output? (or can you hint about the solution)?

$\endgroup$
12
  • $\begingroup$ Kotlin-specific questions are off-topic here. $\endgroup$ Commented May 22, 2020 at 10:25
  • $\begingroup$ Moreover, I don't understand what you're looking for. What is the input, and what is the required output? $\endgroup$ Commented May 22, 2020 at 10:25
  • 1
    $\begingroup$ Your current code considers all pairs of people out of both men and women at the same time. This means that you're also considering homosexual pairs. I have absolutely no problem with that, but I suspect that it's not what you intended. $\endgroup$ Commented May 22, 2020 at 11:25
  • 1
    $\begingroup$ The term "dating" has very specific connotations in English. $\endgroup$ Commented May 22, 2020 at 11:35
  • 4
    $\begingroup$ The general problem you're describing here seems to be finding a schedule for a round-robin tournament. There are many ways to construct such a schedule, some of them listed here. However, the link you give already describes a way to get a round-robin schedule, known as the "circle method". Do you want to find a different method? Or is there something you want to know about the method given in the link? $\endgroup$
    – Discrete lizard
    Commented May 22, 2020 at 11:50

1 Answer 1

5
$\begingroup$

Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$.

Case 1: $n$ is even. In this case, $K_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ edges. Hence we can hope for a partition of $K_n$ into $n-1$ perfect matchings. This is a standard problem, known as 1-factorization of the complete graph. Here is one solution: $$ (0,n-1),(1,n-2),(2,n-3),(3,n-4),\ldots,(n/2-1,n/2) \\ (1,n-1),(2,0),(3,n-2),(4,n-3),\ldots,(n/2,n/2+1) \\ (2,n-1),(3,1),(4,0),(5,n-2),\ldots,(n/2+1,n/2+2) \\ \ldots $$ Explanation: the $i$'th row consists of $(i,n-1)$ together with $(j+i,n-1-j+i \bmod n-1)$ for $1 \leq j \leq n/2-1$. For example, when $n = 6$ you get: $$ (0,5),(1,4),(2,3) \\ (1,5),(2,0),(3,4) \\ (2,5),(3,1),(4,0) \\ (3,5),(4,2),(0,1) \\ (4,5),(0,3),(1,2) $$

Case 2: $n$ is odd. In this case, $K_n$ still contains $\binom{n}{2}$ edges, but now each matching contains at most $(n-1)/2$ edges. Hence we can hope for a partition of $K_n$ into $n$ almost-perfect matchings. We can take the solution above for $n+1$, and just ignore the match of vertex $n$. This gives the following solution: $$ (1,n-1),(2,n-2),(3,n-3),\ldots,((n-1)/2,(n+1)/2) \\ (2,0),(3,n-1),(4,n-2),\ldots,((n+1)/2,(n+3)/2) \\ (3,1),(4,0),(5,n-1),\ldots,((n+3)/2,(n+5)/2) \\ \ldots $$ Explanation: the $i$th row consists of $(j+i,n-j+i \bmod n)$ for $1 \leq j \leq (n-1)/2$. For example, when $n = 7$ you get: $$ (1,6),(2,5),(3,4) \\ (2,0),(3,6),(4,5) \\ (3,1),(4,0),(5,6) \\ (4,2),(5,1),(6,0) \\ (5,3),(6,2),(0,1) \\ (6,4),(0,3),(1,2) \\ (0,5),(1,4),(2,3) $$

$\endgroup$
5
  • $\begingroup$ this is awesome. thank you very much! now I'll try to implement it :D $\endgroup$ Commented May 22, 2020 at 12:47
  • $\begingroup$ I must be doing something wrong pl.kotl.in/HG9uJ5cjX For the n=6, I copied the formula but I get different results. I will try in paper to see what I missed. Is it some parentheses missing? $\endgroup$ Commented May 23, 2020 at 11:34
  • $\begingroup$ are parentheses missing for the mod? I added them pl.kotl.in/HtwQIUgl0 still not perfect but close $\endgroup$ Commented May 23, 2020 at 11:48
  • 2
    $\begingroup$ For me the precedence of mod is lowest, which is equivalent to adding parenthesis to the entire expression on left and right. However, even better is to try to figure out the formula from the examples. $\endgroup$ Commented May 23, 2020 at 12:27
  • $\begingroup$ For the even case, I think you meant j + 1 mod n - 1 (and mod n for the odd case) $\endgroup$
    – user
    Commented May 23, 2020 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.