algorithm - Divvying people into rooms by last name? -

i teach large introductory programming classes (400 - 600 students) , when exam time comes around, have split class different rooms in order make sure has seat exam.

to keep things logistically simple, break class apart last name. example, might send students last names - h 1 room, last name - l second room, m - s third room, , t - z fourth room.

the challenge in doing rooms have wildly different capacities , can hard find way segment class in way causes fit. example, suppose distribution of last names (for simplicity) following:

• last name starts a: 25
• last name starts b: 150
• last name starts c: 200
• last name starts d: 50

suppose have rooms capacities 350, 50, , 50. greedy algorithm finding room assignment might sort rooms descending order of capacity, try fill in rooms in order. this, unfortunately, doesn't work. example, in case, right option put last name in 1 room of size 50, last names b - c room of size 350, , last name d room of size 50. greedy algorithm put last names , b 350-person room, fail find seats else.

it's easy solve problem trying possible permutations of room orderings , running greedy algorithm on each ordering. either find assignment works or report none exists. however, i'm wondering if there more efficient way this, given number of rooms might between 10 , 20 , checking permutations might not feasible.

to summarize, formal problem statement following:

you given frequency histogram of last names of students in class, along list of rooms , capacities. goal divvy students first letter of last name each room assigned contiguous block of letters , not exceed capacity.

is there efficient algorithm this, or @ least 1 efficient reasonable room sizes?

edit: many people have asked contiguous condition. rules are

• each room should assigned @ block of contiguous letters, and
• no letter should assigned 2 or more rooms.

for example, not put - e, h - n, , p - z same room. not put - c in 1 room , b - d in another.

thanks!

it can solved using sort of dp solution on [m, 2^n] space, m number of letters (26 english) , n number of rooms. m == 26 , n == 20 take 100 mb of space , ~1 sec of time. below solution have implemented in c# (it compile on c++ , java too, several minor changes needed):

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];      (int = 0; <= numberofletters; i++)         (int j = 0; j < roomsets; j++)             map[i, j] = -2;      map[0, 0] = -1; // starting condition      (int = 0; < numberofletters; i++)         (int j = 0; j < roomsets; j++)             if (map[i, j] > -2)             {                 (int k = 0; k < numberofrooms; k++)                     if ((j & (1 << k)) == 0)                     {                         // room empty yet.                         int roomcapacity = rooms[k];                         int t = i;                         (; t < numberofletters && roomcapacity >= studentsperletter[t]; t++)                             roomcapacity -= studentsperletter[t];                          // marking next state good, specifying index of occupied room                         // - construct solution backwards.                         map[t, j | (1 << k)] = k;                     }             }      // constructing solution.     int[] res = new int[numberofletters];     int lastindex = numberofletters - 1;     (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];             (; lastindex >= 0 && roomcapacity >= studentsperletter[lastindex]; lastindex--)             {                 res[lastindex] = lastroom;                 roomcapacity -= studentsperletter[lastindex];             }              roommask ^= 1 << lastroom; // remove last room set.              j = roomsets; // on outer loop.         }     }      return lastindex > -1 ? null : res; } 

example op question:

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

answer be:

2 0 0 1 

which indicates index of room each of student's last name letter. if assignment not possible solution return null.

---

[edit]

after thousands of auto generated tests friend has found bug in code constructs solution backwards. not influence main algo, fixing bug exercise reader.

the test case reveals bug students = [13,75,21,49,3,12,27,7] , rooms = [6,82,89,6,56]. solution return no answers, there answer. please note first part of solution works properly, answer construction part fails.