如何生成组合全局唯一的固定大小分块，实现人员最优配对？

需求描述 #

我需要将整数列表（记为 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]

因为 [1,2] 这个组合重复出现了。

可行的输出结果如下（暂不确定是否为唯一解）：

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],  ???  -> 无法再使用已出现过的[4,6]!

我的现有逻辑是先取出指定大小的所有可能组合，再基于这些组合拼接分块，Swift实现代码如下：

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人名单需要6周才能完成全部匹配（最优为5周），且部分周次会有人员无会面安排。该方案可通过下表直观展示（字母代表列表元素/人员，数字代表分块/周次编号），核心逻辑是每列的数字逐行向上偏移1位，忽略元素与自身的配对：

但该方案无法满足我的需求，因为会多出1个分块（即多耗费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 |   |

示例
周1: [F,B], [E,C] （[A,D] 为未匹配项）
周2: [A,B], [C,F], [D,E]
// ...

你原有方案的问题在于贪心取第一个符合条件的配对，容易提前耗尽后续轮次需要的组合，导致局部死锁。针对2人配对的场景，直接使用循环赛圆法即可，这是经过数学证明的最优构造算法，不会出现重复配对，且轮次最少：

• 偶数个人员：共总人数-1轮，每轮所有人都完成配对，无轮空
• 奇数个人员：共总人数轮，每轮仅1人轮空

算法逻辑 #

1. 预处理：如果总人数为奇数，先添加1个虚拟占位元素，和占位元素配对的人员当轮轮空，保证总人数为偶数
2. 固定第一个元素的位置，剩余元素排成环形
3. 每轮配对规则：左右两列同位置元素配对
4. 每轮结束后，除了第一个固定元素，剩余所有元素顺时针旋转1位
5. 共生成总人数-1轮即为全部最优分块

Swift 适配伪代码 #

// 可直接基于你的现有类型改造，虚拟占位可根据你的业务自定义，比如用Optional<T>的nil或者自定义标识
func generateOptimalSchedules<T: Hashable>(elements: [T]) -> [Partition<T>] {
    var items = elements
    let originalCount = items.count
    let hasDummy = originalCount % 2 != 0
    // 补占位元素
    if hasDummy {
        // 这里填入你的自定义占位标识，比如特殊值或者nil
        items.append(/* 占位元素 */ as! T)
    }
    let totalCount = items.count
    let totalRounds = totalCount - 1
    let halfCount = totalCount / 2
    var result = [Partition<T>]()
    
    for _ in 0..<totalRounds {
        var pairs = [Pair<T>]()
        var unmatched = [T]()
        // 固定第一个元素和最后一个元素配对
        let firstItem = items[0]
        let lastItem = items[totalCount - 1]
        if hasDummy && lastItem == /* 你的占位元素判断 */ {
            unmatched.append(firstItem)
        } else {
            pairs.append(Pair(x: firstItem, y: lastItem))
        }
        // 剩余元素左右配对
        for i in 1..<halfCount {
            let left = items[i]
            let right = items[totalCount - 1 - i]
            pairs.append(Pair(x: left, y: right))
        }
        result.append(Partition(matches: pairs, unmatched: unmatched))
        // 旋转：除第一个元素外，最后一个元素插入到第二个位置
        let rotateItem = items.removeLast()
        items.insert(rotateItem, at: 1)
    }
    return result
}

如果需要支持大于2的任意组合大小，属于组合设计理论中的Steiner系统构造问题，通用最优解实现复杂度较高，若你的核心场景是2人配对，上述方案完全满足需求。

内容的提问来源于stack exchange，提问作者Aviel Gross