I`m trying to create an algorithm which creates unique pairs out of an even number of n people. Afterwards it should partition these pairs into n-1 days. so every day, every person meets someone else. pairs shouldn't be duplicated. the algorithm should provide a different solution every time it runs.
e.g. my start array is [1,2,3,4] - this gets converted into following pairs:
[1,2],[1,3],[1,4],
[2,3],[2,4],
[3,4]
now these pairs need to be split up between n-1 days like this
day 1 [1,2] & [3,4]
day 2 [1,3] & [2,4]
day 3 [1,4] & [2,3]
thanks for your help!
UPDATE
Thanks to the answers I wrote this solution
fun createDates(userIds: List<Int>): List<DateEntity> {
val dates = ArrayList<DateEntity>()
val userCount = userIds.size
val days = userCount - 1
val half = userCount / 2
val mutableUsers = userIds.toMutableList()
for (day in 0 until days) {
val firstHalf = mutableUsers.slice(0 until half)
val secondHalf = mutableUsers.slice(half until userCount).reversed()
for (i in firstHalf.indices) {
dates.add(DateEntity(day, firstHalf[i], secondHalf[i]))
}
// rotating the array
mutableUsers.add(1, mutableUsers.removeLast())
}
return dates
}
Round-robin algorithm:
Put people in two rows.
Every day person from the top row is paired with corresponding one from lower row. If number of persons is odd, one person waits for a day.
day 1
A B C
D E F
A:D B:E C:F
After the day shift all but the first person in cyclic manner:
day 2
A D B
E F C
A:E D:F B:C
day 3
A E D
F C B
A:F E:C D:B
and so on.