用姓氏将人分成房间？

Question

我经常教授大型入门编程课程(400-600名学生),当考试时间到来时,我们经常需要将课程分成不同的房间,以确保每个人都有考试的席位.

为了保持后勤方面的简单,我通常会将姓名分开.例如,我可能会将姓氏为A - H的学生发送到一个房间,将姓氏I - L发送到第二个房间,将M - S发送到第三个房间,将T - Z发送到第四个房间.

这样做的挑战是房间通常具有截然不同的容量,很难找到一种方法来分类,使每个人都适应.例如,假设姓氏的分布是(为简单起见)以下内容:

• 姓氏以A:25开头
• 姓氏以B:150开头
• 姓氏以C:200开头
• 姓氏以D:50开头

假设我有容量350,50和50的房间.用于查找房间分配的贪婪算法可能是将房间按容量降序排序,然后尝试按该顺序填写房间.不幸的是,这并不总是奏效.例如,在这种情况下,正确的选项是将姓氏A放在一个大小为50的房间中,将姓氏B-C放入大小为350的房间,将姓氏D放入另一个大小为50的房间.贪婪算法将将姓氏A和B放入350人的房间,然后找不到其他人的座位.

通过尝试房间排序的所有可能排列,然后在每个排序上运行贪婪算法,很容易解决这个问题.这将找到有效的作业或报告不存在的作业.但是,我想知道是否有更有效的方法来做到这一点,因为房间的数量可能在10到20之间,并且检查所有排列可能是不可行的.

总而言之,正式的问题陈述如下:

您将获得班级学生姓氏的频率直方图,以及房间列表和容量.您的目标是通过姓氏的第一个字母对学生进行分配,以便为每个房间分配一个连续的字母块,但不超过其容量.

是否有一个有效的算法,或至少一个有效的合理房间大小？

编辑:很多人都问过连续的情况.规则是

• 每个房间最多应分配一块连续的字母,和
• 不应将信件分配给两个或更多房间.

例如,你不能把A - E,H - N和P - Z放在同一个房间里.你也可以不把A - C放在一个房间里而将B - D放在另一个房间里.

谢谢!

Answer 1

它可以使用某种[m, 2^n]空间的DP解决方案来解决,其中m是字母数(英语为26),n是房间数.与m == 26和n == 20将需要大约100 MB的空间和时间〜1秒.下面是我刚刚在C#中实现的解决方案(它也将在C++和Java上成功编译,只需要几个小的改动):

int[] GetAssignments(int[] studentsPerLetter, int[] rooms)
{
    int numberOfRooms = rooms.Length;
    int numberOfLetters = studentsPerLetter.Length;
    int roomSets = 1 << numberOfRooms; // 2 ^ (number of rooms)
    int[,] map = new int[numberOfLetters + 1, roomSets];

    for (int i = 0; i <= numberOfLetters; i++)
        for (int j = 0; j < roomSets; j++)
            map[i, j] = -2;

    map[0, 0] = -1; // starting condition

    for (int i = 0; i < numberOfLetters; i++)
        for (int j = 0; j < roomSets; j++)
            if (map[i, j] > -2)
            {
                for (int k = 0; k < numberOfRooms; k++)
                    if ((j & (1 << k)) == 0)
                    {
                        // this room is empty yet.
                        int roomCapacity = rooms[k];
                        int t = i;
                        for (; t < numberOfLetters && roomCapacity >= studentsPerLetter[t]; t++)
                            roomCapacity -= studentsPerLetter[t];

                        // marking next state as good, also specifying index of just occupied room
                        // - it will help to construct solution backwards.
                        map[t, j | (1 << k)] = k;
                    }
            }

    // Constructing solution.
    int[] res = new int[numberOfLetters];
    int lastIndex = numberOfLetters - 1;
    for (int j = 0; j < roomSets; j++)
    {
        int roomMask = j;
        while (map[lastIndex + 1, roomMask] > -1)
        {
            int lastRoom = map[lastIndex + 1, roomMask];
            int roomCapacity = rooms[lastRoom];
            for (; lastIndex >= 0 && roomCapacity >= studentsPerLetter[lastIndex]; lastIndex--)
            {
                res[lastIndex] = lastRoom;
                roomCapacity -= studentsPerLetter[lastIndex];
            }

            roomMask ^= 1 << lastRoom; // Remove last room from set.

            j = roomSets; // Over outer loop.
        }
    }

    return lastIndex > -1 ? null : res;
}

OP问题的例子:

int[] studentsPerLetter = { 25, 150, 200, 50 };
int[] rooms = { 350, 50, 50 };
int[] ans = GetAssignments(studentsPerLetter, rooms);

答案是:

2
0
0
1

这表示每个学生的姓氏字母的空间索引.如果无法分配,我的解决方案将返回null.

[编辑]

经过数千次自动生成测试后,我的朋友发现代码中存在一个错误,后者构建了解决方案.它不影响主要算法,因此修复此错误将是读者的练习.

揭示错误的测试用例是students = [13,75,21,49,3,12,27,7]和rooms = [6,82,89,6,56].我的解决方案没有回答,但实际上有一个答案.请注意,解决方案的第一部分工作正常,但答案构造部分失败.