我正试图将一个整数列表(比如elements(分解为所有可能的分区，这些分区具有相同大小的组合(比如n(，其中这些组合在不同分区之间是唯一的，而不仅仅是在同一分区内。
用例是，我有一个人员列表，我需要匹配他们，以便他们在最短的时间内只见面一次。因此，对于每周10人的会议列表，以及1:1的会议(每个组合2人(，他们都可以在9周内见面。
可以采用任何组合尺寸的解决方案都是理想的，但只适用于尺寸2的解决方案也很棒。
示例
例如，如果列表为[1,2,3,4,5,6]。我们不能同时拥有这两个分区：
[1,2], [3,5], [4,6]
[1,2], [3,4], [5,6]
因为CCD_ 4被找到两次。。。
一个可能的结果(或者唯一不确定的结果(是：
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]
我试了什么
这是非常天真的，不起作用，因为它最终会做这样的事情：
1: [1,2], [3,5], [4,6]
2: [1,3], [2,5], ??? -> Can't do [4,6] again!
它基本上得到了特定大小的所有可能的组合，然后尝试从中生成分区。
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
(我正在使用Swift，但很乐意接受任何语言或伪逻辑的建议！只要它能避免我不确定如何翻译的事情，比如Python的yield等。(
我还知道一种方法，可以获得组合为2的分区，其中每个分区正好有1个重复的组合。回到用例，这意味着我将在6周内(而不是5周(匹配一个6人的列表，并且会有几周的时间，几个人不会开会。该解决方案可以很容易地显示在一个小表中(字母是列表中的元素/人员，数字是分区/周数(。它本质上只是将每列中的数字向上移动1行，忽略元素本身的成对…
我不能使用这个解决方案，因为它意味着要有另一个分区(即，再多一周(。。。
| | 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]
// ...
组合大小为2的答案是Round Robin算法的实现，@RaffleBuffel在评论中提到了这一点。
以下是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
}
然后我们可以得到结果：
for round in roundRobin(teams: 12) {
print(round)
}
打印：
[[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]]