Search code examples
javapythonalgorithmkotlinlogic

Algorithm to distribute n people in unique pairs over n-1 days


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
    }

Solution

  • 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.