Find unique partitions from combinations of certain size

Question

I am trying to break a list of integers (say elements) into all of its possible partitions with combinations of the same size (say n), where the combinations are unique across different partitions, not just within the same partition.

The use case is that I have a list of people, and I need to match them so they all meet each other exactly once, in the minimum amount of time. So for a list of 10 people meeting weekly, and meetings of 1:1 (2 people in each combination), they can all meet each other in 9 weeks.

A solution that can take any combination size is ideal, but one that only works for size 2 is also great.

Example

For example, if the list is [1,2,3,4,5,6]. We can't have both of these partitions:

[1,2], [3,5], [4,6]
[1,2], [3,4], [5,6]

because then [1,2] is found twice...

A possible result (or the only? not sure) is:

1: [1,2], [3,4], [5,6]
2: [1,3], [2,5], [4,6]
3: [1,4], [2,6], [3,5]
4: [1,5], [2,4], [3,6]
5: [1,6], [2,3], [4,5]

What I tried?

This is very naive and does not work, because it ends up doing something like this:

1: [1,2], [3,5], [4,6]
2: [1,3], [2,5],  ???  -> Can't do [4,6] again!

It basically gets all possible combinations of a certain size, then tries to make the partitions from them.

var result = [Partition<T>]()
var combinations = elements.combinations(ofCount: 2)

while !combinations.isEmpty {

    var pairs = [Pair<T>]()
    var elementsLeft = elements

    while elementsLeft.count > 1 {
        let aPair = combinations.first { elementsLeft.contains($0.x) && elementsLeft.contains($0.y) }!
        combinations.remove(aPair)
        elementsLeft.remove(aPair.x)
        elementsLeft.remove(aPair.y)
        pairs.append(aPair)
    }

    let partition = Partition(matches: pairs, unmatched: Array(elementsLeft))
    result.append(partition)
}

return result

(I am using Swift, but will happily take advice in any language or pseudo logic! As long as it avoids things I am not sure how to translate like Python's yield etc.)

I also know of a way to get partitions with combinations of 2 where each partition has exactly 1 duplicated combination. Going back to the use case, it means I will match a list of 6 people in 6 weeks (instead of 5), and that there will be weeks where a couple of people won't have a meeting. That solution can be easily shown in a small table (letters are elements/people in the list, numbers are partition/week number). It essentially just involves shifting the numbers up by 1 row in each column, ignoring pairs of an element with itself…

I can't use this solution because it means having another partition (ie, one more week)...

|   | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A |   | 2 | 3 | 4 | 5 | 6 |
| B | 2 |   | 4 | 5 | 6 | 1 |
| C | 3 | 4 |   | 6 | 1 | 2 |
| D | 4 | 5 | 6 |   | 2 | 3 |
| E | 5 | 6 | 1 | 2 |   | 4 |
| F | 6 | 1 | 2 | 3 | 4 |   |

eg
week 1: [F,B], [E,C] (where [A,D] "unmatched")
week 2: [A,B], [C,F], [D,E]
// ...

yes, then each partition has "leftover", so eg in a list of 7 you would have 6 (I think?) partitions where each of the elements is left in one of the partitions — Aviel Gross, Jul 06 '21 at 16:33
Does [Round Robin Scheduling](https://stackoverflow.com/questions/6648512/scheduling-algorithm-for-a-round-robin-tournament/6649732#6649732) work for you? — RaffleBuffle, Jul 06 '21 at 17:33
I think it does!! I did not know this is how it's called, thank you! I will run a few tests to ensure this covers it and write the solution here, unless you want to add it I'll happily accept your answer (: — Aviel Gross, Jul 06 '21 at 18:30
If that old answer is the exact answer to this question then this question is a duplicate, and should be closed. Unless you want the answer for tuples too.. — Dialecticus, Jul 06 '21 at 19:39

score 1 · Accepted Answer · answered Jul 07 '21 at 14:36

The answer for a combination size of 2 is an implementation of the Round Robin algorithm, as mentioned by @RaffleBuffle in the comment.

Below is an implementation in Swift:

func roundRobin(teams n: Int) -> [[[Int]]] {
    var rounds = [[[Int]]]()
    var aRound = [[Int]]()
    var aMatch = [Int]()
    for r in 1..<n {
        for i in 1...n/2 {
            if (i == 1) {
                aMatch.append(1)
                aMatch.append((n-1+r-1) % (n-1) + 2)
            } else {
                aMatch.append((r+i-2) % (n-1) + 2)
                aMatch.append((n-1+r-i) % (n-1) + 2)
            }
            aRound.append(aMatch)
            aMatch = []
        }
        rounds.append(aRound)
        aRound = []
    }
    return rounds
}

We can then get the results:

for round in roundRobin(teams: 12) {
    print(round)
}

Which prints:

[[1, 2], [3, 12], [4, 11], [5, 10], [6, 9], [7, 8]]
[[1, 3], [4, 2], [5, 12], [6, 11], [7, 10], [8, 9]]
[[1, 4], [5, 3], [6, 2], [7, 12], [8, 11], [9, 10]]
[[1, 5], [6, 4], [7, 3], [8, 2], [9, 12], [10, 11]]
[[1, 6], [7, 5], [8, 4], [9, 3], [10, 2], [11, 12]]
[[1, 7], [8, 6], [9, 5], [10, 4], [11, 3], [12, 2]]
[[1, 8], [9, 7], [10, 6], [11, 5], [12, 4], [2, 3]]
[[1, 9], [10, 8], [11, 7], [12, 6], [2, 5], [3, 4]]
[[1, 10], [11, 9], [12, 8], [2, 7], [3, 6], [4, 5]]
[[1, 11], [12, 10], [2, 9], [3, 8], [4, 7], [5, 6]]
[[1, 12], [2, 11], [3, 10], [4, 9], [5, 8], [6, 7]]

Find unique partitions from combinations of certain size

Example

What I tried?

1 Answers1