将一组人分成有约束的小组

Question

所以我想写一个小程序，它能够把一群人(100-200)分成几个有约束的平等的组(10-15)。

每个人都有他们来自的城市(通常总共有8-12个不同的城市)。在这个新的部门之前，每个人都属于一组人(10-20个不同的组)。这就是我们的例子。

现在我想把这些人分成不同的组，这样我们就可以努力让每个团队中来自不同城市的人数相同(所以不是所有的纽约人都在同一个团队中，等等)，并努力让以前在同一个团队中的人不会再组合在一起。

找不到可以帮助我的算法。

Answer 1

找到一个绝对的最佳答案有一种np-complete的感觉。但是你只是想要一个非常好的答案，非常快，想出一个启发式并不难。

建立你的空团队。决定团队的最大规模。根据要避免(同一城市或过去的同一团队)下降的其他人的数量对人员进行排序。将每个人放在非完整团队中，与你试图避免的其他最少的人在一起，与较小的人打破团队的关系，并随机打破任何剩余的关系。

这并不能保证产生最佳结果。但它很简单，而且会产生相当好的结果。