-
Notifications
You must be signed in to change notification settings - Fork 0
/
k1-k2-roommates.py
128 lines (94 loc) · 3.55 KB
/
k1-k2-roommates.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import utils
from random import randint, shuffle
parameters = {
"group_sizes_conv": 20,
"create_solution_conv": 20,
"3_permutation_conv": 20,
"2_permutation_conv": 20,
}
def generate_group_sizes(n, m_min, m_max):
""" Generate different group sizes g1 .. gq between m_min
and m_max where g1 + .. + gq = n """
if m_min == m_max:
if n % m_min == 0:
return [m_min] * (n // m_min)
else:
return None
if n < m_min:
return None
l = list(range(m_min, m_max + 1))
shuffle(l)
while len(l) > 0:
group_size = l.pop()
# TODO: improve this
attribution = generate_group_sizes(n - group_size, m_min, min(m_max, group_size))
if attribution is not None:
return [group_size] + attribution
return None
def create_solution(n, preferences, group_sizes):
""" Create a solution from the preferences and the group sizes given.
Start from a random solution and do 2-permutation until no 2-permutation
can improve the score. Then do a 3-permutation to keep on improving the score. """
solution = list(range(0, n))
shuffle(solution)
actual_score = utils.compute_score_att(preferences, solution, group_sizes)
no_chgt = 0
no_chgt_3_switch = 0
while no_chgt_3_switch < parameters["3_permutation_conv"]:
while no_chgt < parameters["2_permutation_conv"]:
a1 = randint(0, n - 1)
a2 = randint(0, n - 1)
solution[a1], solution[a2] = solution[a2], solution[a1]
new_score = utils.compute_score_att(preferences, solution, group_sizes)
if new_score < actual_score:
no_chgt = 0
actual_score = new_score
else:
no_chgt += 1
solution[a1], solution[a2] = solution[a2], solution[a1]
no_chgt_3_switch += 1
b1 = randint(0, n - 1)
b2 = randint(0, n - 1)
b3 = randint(0, n - 1)
temp_var = solution[b1]
solution[b1] = solution[b2]
solution[b2] = solution[b3]
solution[b3] = temp_var
new_score = utils.compute_score_att(preferences, solution, group_sizes)
if new_score < actual_score:
no_chgt_3_switch = 0
actual_score = new_score
else:
temp_var = solution[b3]
solution[b3] = solution[b2]
solution[b2] = solution[b1]
solution[b1] = temp_var
return solution, actual_score
def solve_m_roommates(n, m_min, m_max, preferences):
""" Group the n people by m1 to m2.
Start by a random solution and make some 2-permutations. """
group_sizes = generate_group_sizes(n, m_min, m_max)
solution = list(range(0, n))
shuffle(solution)
actual_score = utils.compute_score_att(preferences, solution, group_sizes)
no_chgt = 0
no_chgt_group_size = 0
while no_chgt_group_size < parameters["group_sizes_conv"]:
new_group_size = generate_group_sizes(n, m_min, m_max)
no_chgt_group_size += 1
while no_chgt < parameters["create_solution_conv"]:
new_solution, new_score = create_solution(n, preferences, new_group_size)
no_chgt += 1
if new_score < actual_score:
actual_score = new_score
solution = new_solution
group_sizes = new_group_size
no_chgt = 0
no_chgt_group_size = 0
return solution, group_sizes
if __name__ == "__main__":
n, m_min, m_max, preferences = utils.get_preferences("data/sample_2.txt")
solution, group_sizes = solve_m_roommates(n, m_min, m_max, preferences)
score = utils.compute_score_att(preferences, solution, group_sizes)
print(f"Found a solution with a score of {score}")
utils.save_solution_att("output/solution_" + str(m_min) + "_" + str(m_max) + "_" + str(score) + ".txt", solution, group_sizes)