如何以随机顺序生成所有集合组合

Question

首先,我甚至不确定术语是否正确,因为我没有找到类似的东西(特别是因为我甚至不知道要使用哪些关键字)

问题: 有一群人,我想把他们分成小组.我有一套规则可以为每个作业分配一个分数.我想找到最好的一个(或者至少是一个非常好的).

例如,如果人口为4,{A,B,C,D}并分配给两组,则可能的分配是:

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

例如,{B,A},{C,D}并且{C,D},{A,B}它们都与第一个相同(我不关心组内的顺序和组本身的顺序).

人数,群体数量以及每个群体中适合的人数都是投入.

我的想法是列出每个可能的分配,计算他们的分数并跟踪最好的分配.也就是说,蛮力.由于人口可能很大,我想以随机顺序浏览它们并返回时间用完时找到的最好的一个(可能是当用户感到无聊或认为它是一个足够好的发现时).人口可以从非常小(列出的四个)到非常大(可能超过200个)变化,所以只是尝试随机的而不关心重复与小的一起分解,在那里可能有蛮力(加上我不知道什么时候)如果我使用普通随机排列,则停止).

人口足够大,列出能够改组它们的所有分配都不适合记忆.所以我需要一个方法来以随机顺序查找所有可能的赋值,或者一个方法,给定一个索引,生成相应的赋值,并使用索引数组和shuffle(第二个会更好因为我可以很容易将任务分配到多个服务器中).

Answer 1

如果您的人口足够多，无法在内存中容纳所有分配，并且不太可能测试所有可能的分配，那么最简单的方法就是随机选择测试分配。例如：

repeat 
    randomly shuffle population
    put 1st n/2 members of the shuffled pop into assig1 and 2nd n/2 into assig2
    score assignation and record it if best so far
until bored

如果您的人口众多，则不太可能会因重复测试而造成很大的效率损失，因为您不太可能再次遇到相同的分配。

根据您的评分规则，选择下一个要测试的分配可能会更有效，例如在迄今为止找到的最佳分配之间交换一对成员，但您没有提供足够的信息来确定情况是否如此。