Put n persons in x 2-Beds-Room and y 3-Beds-Room based on preferences

Question

I have troubles solving the following Problem for a class-trip:

There are 54 students who have to be divided into 14 3-bed rooms and 6 2-bed rooms. Each person has one or more favorites with whom he/she would like to share a room.

preferences = {'studen1': [studnet2, student3], 'student2': [student3, student 1], ...}

I was able to calculate every possible triple match (in a group of 3 students everyone likes each other back) and normal match (in a group of 2 students everyone likes each other back)

I thought about maybe trying to calculate every possible combinations of students (or at least the preverences) and try to get the best result by providing points based on how good the rooms are: good 3-person room: 6 points good 2 room: 4 points average 3-person room: 5 points average 3-bed room: 4 points medium bad 3 room: 3 points bad 3er room: 2 points very bad 3-bed room: 1 point medium 2 room: 1 point

Now I am sorta overwhelmed an don't know how to approach the problem without having the need of using a super-computer ;)

I am sorry for my very bad code ;) this is my code after calculating the normal and triple matches:

students_with_room = []
real_rooms = []

exit_loop = False

real_rooms = {'2A': [], '2B': [], '2C': [], '2D': [], '2E': [], '2F': [],'3A': [], '3B': [], '3C': [], '3D': [], '3E': [], '3F': [], '3G': [], '3H':    [], '3I': [], '3J': [], '3K': [], '3L': [], '3M': [], '3N': [],}    
for student in students:
    if student not in students_with_room: 
        if triple_matches[student] == None:
            for room in real_rooms:
                if real_rooms[room] == [] and '2' in room:
                    if len(matches[student]) != 0:
                        for i in range(len(matches[student])):
                                if len(set([matches[student][i], student]).intersection(students_with_room)) == 0:
                                    real_rooms[room] = [matches[student][i], student]                        
                                    students_with_room = students_with_room + [matches[student][i]]
                                    students_with_room = students_with_room + [student]
                                    exit_loop = True
                                    break   
                                else: 
                                    pass


                    else: 
                        pass  
                if exit_loop == True:
                    break   
                if real_rooms[room] == [] and '3' in room:
                    pass    
            exit_loop = False   
        else:
            for room in real_rooms: 
                if student not in students_with_room:   
                    if real_rooms[room] == [] and '3' in room:
                        real_rooms[room] = [triple_matches[student][0], triple_matches[student][1], student]                        
                        students_with_room = students_with_room + triple_matches[student]
                        students_with_room = students_with_room + [student]
    else: 
        pass

for triple_match in triple_matches:
    already_done = False
    if triple_matches[student] == None:
        pass
   
    else:            
        if student in students_with_room:
            already_done = True 
        if not already_done:
            students_with_room.append(triple_matches[student][0])
            real_rooms

Answer 1

Alright so this problem seemed kind of interesting, here is an example of a simple but brute force solution using networkx. Note that this will run slowly once your number of students grows to be large. I would still recommend treating this as a multiple knapsacks problem, but hopefully this enough to get you thinking about the problem a little differently.

import networkx as nx
import itertools
from collections import defaultdict 

preferences = {"A":["B", "C", "F"], 
               "B":["A", "D"],
               "C":["A", "D"], 
               "D":["C", "B"], 
               "E":["F", "G"],
               "F":["G", "A"],
               "G":["F", "D"],
              }
# Here we build a complete graph, i.e. any student can stay with 
# Another student. Note: If you have directional relationships, 
# i.e. student A likes student B, but student B does not like 
# Student a, you'll need to change this to a directed graph and 
# update how the path weights are calculated accordingly. 
G = nx.complete_graph(preferences.keys())

N_HOTEL_ROOMS = 3

student_ids = list(preferences.keys())
for key in student_ids:
    for k in student_ids:
        if k in preferences[key]:
            # arbitrary value, if two students like eachother
            G[key][k]['weight'] = 2
        else:
            # I am lazy
            try:
                # aribtrary value, if two students don'w seem to like eachother
                G[key][k]['weight'] = -1
            except:
                pass
def path_weight(G, path):
    # Function to calculate the weight of a path
    weight = 0
    for i in range(len(path) - 1):
        weight += G[path[i]][path[i + 1]]['weight']
        if len(path) > 1:
            weight += G[path[0]][path[-1]]['weight']
    return weight 

def is_allowed(combination, student_ids = student_ids):
    # Function to see if we have any students in multile rooms 
    #-- if so we can throw away the combination, and we also 
    # want to make sure all students are accounted for 
    all_elements = sum(combination, ())
    counter = defaultdict(int)
    for c in all_elements:
        counter[c] += 1
    return max(counter.values()) <= 1 and set(all_elements) == set(student_ids)

combos = []
# Find unique pairs of two students, so we can find
# which other students will go with them 
room_assignments = [2,3]
for assignment in room_assignments:
    for comb in itertools.combinations(keys, assignment):
        combos.append(comb)
    
paths = {}
# Now for each unique pair of students, find a path of length
# sutends_to_room between them and find the weight of the path
# i.e. the "score" of putting those students to a room

for path in combos:
    weight = path_weight(G,path)
    paths[tuple(path)] = weight

# Get all possible combinations of students between three hotel rooms
allowable = itertools.combinations(paths.keys(), N_HOTEL_ROOMS)
# Only accept solutions where a student isn't between each room, 
# and when we have all students
allowable = [a for a in allowable if is_allowed(a)]

max_paths = {}
for path in allowable:
    max_paths[path] = sum([paths[a] for a in path])
# # sort the result, and the first entry is our "best" solution
s =  dict(sorted(max_paths.items(), key=lambda item: item[1], reverse=True))
room_assignment = list(s.keys())[0]

print("Room assignment", room_assignment, "Happiness score", s[room_assignment])

>>> Room assignment (('A', 'B'), ('C', 'D'), ('E', 'F', 'G')) Happiness score 7

Where here, s is our final allowable combinations, and the key with the largest weight would be our optimal solution -- i.e. the room allocation with the happiest students.

Edit: Apologies, I misread the original question, I did not realize you had set student number assignments between rooms, this should address that.

Answer 2

As a graph theory problem, we can treat the students as nodes, and preference as edges.

Then what you're looking for is a clique cover with 14 K3 and 6 K2.

There's a randomized approach to finding clique covers that can be modified for this, called iterated greedy.

1. Represent each student as a bitvector with a 1 for every compatible student (including onself). E.g. if student 2 was compatible with student 3, then student 2 would have a set bit at positions 2 & 3.
2. Shuffle the student bitvectors.
3. Greedily assign students to the first clique that 1) has room and 2) is compatible. Here, keep track of the count of K3, and drop the max clique size from 3 to 2 once you've hit your limit.
4. Repeat from step 2, until you get the cover you're looking for.

The only change from the normal IG algorithm is that you're capping the clique size, which is an easy modification.

To clarify the greedy assignment step:

• We maintain an array of cliques, empty at the start of step 3.
• The first student in shuffled order always forms the first clique.
• The second student is merged into the first if they're compatible, and the compatibility bitvector of the newly formed clique is the AND of the two bitvectors.
• If the second student isn't compatible with the first, it forms the first node of the second clique.
• Each subsequent student gets merged with the first clique that 1) it's compatible with and 2) has room for it. For the latter, there's no need to assume the first 14 cliques are the K3s. You can just keep a count of K3s and stop making new ones when it hits 14.