如何随机生成组内唯一、全局均衡的整数分组？

我正在开发一个对象间互相指向的程序，每个对象分配有从0开始的整数ID，需求如下：

• 每个对象需选择相同数量的其他对象作为目标，不能指向自身，且同一目标仅被指向一次；
• 每个对象被其他对象指向的次数需相同，避免分布不均。

这可转化为整数分组问题：从指定整数范围生成固定大小的分组，组内元素唯一，所有整数在所有分组中的总出现次数相同，后续可单独处理分组排除自身ID的情况。

尝试方案1：猜测验证法 #

这是一种简单的猜测验证思路，随机生成分组并剔除无效值。该方案虽能完成任务，但存在效率低下、可能陷入无限循环的问题，代码如下：

import random
from typing import Tuple, Set, Iterator

def randTargets(numObjs:int, numTargets:int) -> Iterator[Tuple[int, Set[int]]]:
    # numObjs 是对象总数
    # numTargets 是每个对象要指向的其他对象数量
    # numTargets 范围可假定为 [2, numObjs)
    numLeft = [numTargets] * numObjs
    # numLeft 表示每个对象还能被指向的次数
    # 比如 numLeft[i] = n 时，i 还能被指向 n 次
    
    for i in range(numObjs):
        targets = set()
        # 可能会陷入无限循环：只剩自身ID可选，但暂时没处理
        # 先假设这种情况不会发生
        
        while len(targets) < numTargets:
            t = random.randrange(numObjs)
            # 检查目标不是自身、未被指向次数超限、未被当前对象指向过
            if t != i and numLeft[t] > 0 and t not in targets:
                targets.add(t)
                numLeft[t] -= 1
        yield i, targets
        
    # 验证每个对象都被恰好指向 numTargets 次
    assert all(i == 0 for i in numLeft)

尝试方案2：非完全随机法 #

我尝试改进方案，但实现的方法无法做到完全随机，存在可识别的规律，代码如下：

def randTargetsSlightlyBetter(numObjs:int, numTargets:int) -> Iterator[Tuple[int, Set[int]]]:
    # numObjs 是对象总数
    # numTargets 是每个对象要指向的其他对象数量
    # numTargets 范围可假定为 [2, numObjs)
    objs = list(range(numObjs))
    targets = []
    
    for offset in random.sample(range(1, numObjs), k=numTargets):
        # 将 objs 列表向右偏移 offset 位，循环 wrap
        targets.append(objs[offset:] + objs[:offset])

    for obj, *targets in zip(objs, *targets):
        yield obj, targets

核心需求总结 #

从指定整数范围生成固定大小的随机分组，组内元素不重复，所有整数在所有分组中的总出现次数相同。

示例输出 #

>>>randGroups(range(4), repeats=2)
[{0, 2}, {1, 3}, {0, 3}, {1, 2}]
>>>randGroups(range(10), repeats=3)
[{1, 8, 9}, {1, 2, 8}, {5, 6, 7}, {2, 3, 6}, {4, 5, 9}, {5, 7, 9}, {0, 8, 9}, {0, 2, 8}, {1, 6, 7}, {0, 3, 4}]

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