团队组合集算法

Question

我们有 N 个学生，每个团队有 M 个学生，并且肯定 N 可以被 M 整除。所以递归组合可以解决问题。例如 N=6,N=2

12,34,56 is a combination

13,24,56 is another one

但问题是生成的组合可以像

一样重复

12,34,56

34,12,56

那么有什么算法可以生成不重复的组合集吗？

此外，如果我有一个邻接矩阵

S1 S2 S3 S4 S5 S6 S7 S8 S9

0 1 0 0 0 0 1 0 0 0

1 0 0 1 0 0 1 0 1 0

0 0 0 1 0 0 0 1 0 0

0 1 1 0 0 1 0 1 0 0

0 0 0 0 0 1 0 0 1 0

0 0 0 1 1 0 0 0 0 1

1 1 0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0 0 0

0 1 0 0 1 0 0 0 0 1

0 0 0 0 0 1 0 0 1 0

其中 1 代表哪个学生曾与其他学生合作，我能否生成团队中最多学生合作的组合最多等于 m/2？

Answer 1

我认为解决这个问题的最好方法是为每个学生分配一个队号。因此，如果您有 6 个学生，并且团队必须由 2 个学生组成，那么您必须建立 3 个团队。所以 [0,0,1,1,2,2] 可以代表学生的团队合作方式。

这是一个大小为6（学生人数）的数组，每个位置的值代表分配的队号。如果我没理解错的话，您不想将那个团队与 [1,1,2,2,0,0] 区分开来，因为相同的学生被组合在一起。

我的做法是从左到右为每个学生分配一个队号。第一个学生将始终在 0 队中，对于任何其他学生，只分配一个最多比数组左侧学生中已经使用的最大队号多一个的队号。所以 [0,1,1,2,0,2] 将是学生如何分组的候选表示，但 [0,2,1,1,0,2] 不是，因为位置 1 的学生被分配到小组 2，但小组 1 尚未开始。

创建此类团队的代码可能类似于：

IEnumerable<int[]> CombineTeams(int numberOfStudents, int teamSize) {
    int numberOfTeams = numberOfStudents / teamSize;
    int[] studentsInTeam = new int[numberOfTeams]; // used to avoid assigning more than teamSize students into a same team
    studentsInTeam[0] = 1; // first student is initially assigned to team 0 from the start.
    List<int[]> teams = new List<int[]>(); // here all the possible teams will be stored
    int[] currentTeam = new int[numberOfStudents]; // used to assign the team numbers to studend
    AssignTeams(teamSize, currentTeam, teams, 1, 0, studentsInTeam); // start assigning team numbers from the second student, as the first will always be in team 0
    return teams;
}

void AssignTeams(int teamSize, int[] currentTeam, List<int[]> teams, int currentStudent, int maxTeam, int[] studentsInTeam) {
    if (currentStudent == currentTeam.Length) {
        int[] newTeam = new int[currentStudent];
        for (int s = 0; s < currentStudent; s++)
            newTeam[s] = currentTeam[s];
        teams.Add(newTeam);
    }
    else {
        for (int t = 0; t <= min(maxTeam+1, studentsInTeam.Length-1); t++) {
            if (studentsInTeam[t] < teamSize) {
                studentsInTeam[t]++;
                currentTeam[currentStudent] = t;
                AssignTeams(teamSize, currentTeam, teams, currentStudent+1, max(maxTeam, t), studentsInTeam);
                studentsInTeam[t]--;
            }
        }
    }
}

由于此代码创建了所有可能的组队组合，因此您会在其中找到可以将您的组队连接最大化到 M/2 的组合（如果存在）（没有考虑最后一部分）。希望这对你有用。

团队组合集算法

Combination of Teams Sets Algorithm

algorithm

combinations