将一群人分成有​​约束的团队 [英] Divide a group of people into teams with constraints

问题描述

所以我想写一个小程序，它可以容纳一群人(100-200)，并在有约束的情况下将他们分成几个相等的组(10-15).

So I want to write a small program that would be able to take a group of people (100-200) and divide them into several equal groups (10-15) with constraints.

每个人都有一个城市(通常约有8-12个不同的城市).在这个新部门之前，每个人都是一群人(10-20个不同的小组).就是这个例子.

Each person has a city they came from (usually around 8-12 different cities total). Each person was in a group of people before this new division (10-20 different groups). Thats it for the example.

现在，我想将这些人划分为不同的群体，以便我们努力使每个团队中来自不同城市的人数相同(因此，并非所有纽约人都在同一个团队中，等等)，并努力使曾经在这里工作的人同一支队伍再也不会组队.

Now I want to divide those people in different group such that we strive to have same number of people from different cities in each team (so not all new yorkes are in the same team etc) and strive that people who have been in the same team before wont team up again.

无法找到可以帮助我的算法.

Cant find an algorithm that can help me.

推荐答案

关于找到绝对最佳答案的感觉很完整.但是，您只想一个很好的答案，很快，就很容易提出启发式方法了.

There is an np-complete feeling about finding an absolute best answer. But you just want a pretty good answer, pretty fast, it isn't hard to come up with a heuristic.

建立空团队.确定最大团队规模.按其他人的数量对人进行排序，以避免下降(同一座城市或过去的同一支球队).将每个人与您想避免的其他人一起放在最少的其他人中，与较小的人打破团队的纽带，并随机打破其余的纽带.

Set up your empty teams. Decide on the maximum team size. Sort people by the number of other people to avoid (same city or past same team) descending. Put each person in the non-full team with the least other people you are trying to avoid, breaking ties for the team with smaller people, and randomly breaking any remaining ties.

不能保证产生最佳结果.但这很简单，并且会产生很好的结果.

This is not guaranteed to produce optimal results. But it is simple and will produce pretty good ones.

这篇关于将一群人分成有​​约束的团队的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！