CODEWITHSUNDEEP
javapythonalgorithmkotlinlogic
Toby
Toby

Reputation: 71

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
    }

Upvotes: 1

Views: 205

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50787

This code simply performs the algorithm described by MBo.

const cycle = (n, xs) => 
  [... xs .slice (n % xs .length), ... xs .slice (0, n % xs .length)]

const pairs = (xs) =>
  xs.length < 2 ? [] : [[xs [0], xs [xs .length - 1]], ...pairs (xs .slice (1, -1))]

const roundRobin = ([x, ...xs]) => 
  Array.from(xs, (_, i) => pairs ([x, ...cycle(i, xs)]))

console .log (roundRobin ([1, 2, 3, 4, 5, 6])) //=>
// (1 - 6)  &  (2 - 5)  &  (3 - 4)
// (1 - 2)  &  (3 - 6)  &  (4 - 5)
// (1 - 3)  &  (4 - 2)  &  (5 - 6)
// (1 - 4)  &  (5 - 3)  &  (6 - 2)
// (1 - 5)  &  (6 - 4)  &  (2 - 3)
.as-console-wrapper {max-height: 100% !important; top: 0}

cycle just cycles an array n places, so that, for instance, cycle (2, ['a', 'b', 'c', 'd', 'e']) yields ['c', 'd', 'e', 'a', 'b']. pairs puts into pairs the two elements from the ends of the array and then the two next to them, and so forth. pairs (['a', 'b', 'c', 'd', 'e', 'f']) yields [['a', 'f'], ['b', 'e'], ['c', 'd']].

We combine these in roundRobin, For each day, we remove the first value, cycle the remaining ones, put the first value back, and turn the list into pairs.

If you want additional randomness, I would suggest simply shuffling the array before you start.

If you want to allow an odd number of participants, with one sitting out each time, I would add a dedicated sitting-out participant, which will then be paired each day with a different participant.

Upvotes: 1

MBo
MBo

Reputation: 80187

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.

Upvotes: 3

Related Questions