CODEWITHSUNDEEP
algorithmsortingdivide
Nguyễn Duy
Nguyễn Duy

Reputation: 1

How to best arrange students into different groups?

Problem:

We have 370 students in 31 groups, each student is interested in 1 subject (subject 1 to 6)

We have 4 classrooms, each classroom can accommodate fixed number of students with fixed number of subjects.

How can we best arrange those students into all classrooms so that they can all have their favourite subjects? If that's not possible, return the best option where each classroom accommodates the highest matching percentage.

Given that all students in the same group must go together.

Example:

Students:

{
  'G1': [ { '6': 9 }, 9 ],
  'G2': [ { '6': 7 }, 7 ],
  'G3': [ { '1': 1, '2': 1 }, 2 ],
  'G4': [ { '6': 4 }, 4 ],
  'G5': [ { '6': 2 }, 2 ],
  'G6': [ { '1': 1, '6': 5 }, 6 ],
  'G7': [ { '6': 3 }, 3 ],
  'G8': [ { '6': 2 }, 2 ],
  'G9': [ { '1': 2, '2': 1 }, 3 ],
  'G10': [ { '1': 2, '2': 6, '3': 3, '4': 2 }, 13 ],
  'G11': [ { '6': 13 }, 13 ],
  'G12': [ { '4': 1, '6': 8 }, 9 ],
  'G13': [ { '1': 5, '2': 5, '3': 12, '4': 6 }, 28 ],
  'G14': [ { '3': 9, '4': 3, '6': 8 }, 20 ],
  'G15': [ { '2': 4, '3': 10, '4': 2, '6': 3 }, 19 ],
  'G16': [ { '3': 9, '4': 8, '5': 1, '6': 5 }, 23 ],
  'G17': [ { '2': 2, '3': 3, '6': 19 }, 24 ],
  'G18': [ { '1': 2, '2': 1, '3': 3, '4': 11, '5': 2, '6': 2 }, 21 ],
  'G19': [ { '1': 2, '2': 4, '3': 6, '4': 4, '5': 1, '6': 3 }, 20 ],
  'G29': [ { '2': 3, '3': 13, '5': 1, '6': 6 }, 23 ],
  'G21': [ { '1': 1, '2': 2, '3': 11, '4': 1, '6': 10 }, 25 ],
  'G22': [ { '3': 1, '6': 3 }, 4 ],
  'G23': [ { '3': 1, '4': 1 }, 2 ],
  'G24': [ { '6': 6 }, 6 ],
  'G25': [ { '2': 1 }, 1 ],
  'G26': [ { '2': 3, '3': 4, '4': 14, '5': 2, '6': 5 }, 28 ],
  'G27': [ { '1': 3, '2': 2, '3': 3, '5': 3, '6': 12 }, 23 ],
  'G28': [ { '6': 8 }, 8 ],
  'G29': [ { '2': 3, '3': 5, '4': 5, '5': 3, '6': 1 }, 17 ],
  'G30': [ { '2': 2, '3': 1, '6': 1 }, 4 ],
  'G31': [ { '6': 1 }, 1 ]
}

Classrooms:

{
      '1B': [ { '3': 9, '4': 19, '5': 1, '6': 71 }, 100 ],
      '1A': [ { '1': 11, '2': 19, '3': 33, '4': 1, '6': 16 }, 80 ],
      '2B': [ { '2': 3, '3': 14, '4': 38, '5': 12, '6': 43 }, 110 ],
      '2A': [ { '1': 8, '2': 18, '3': 38, '6': 16 }, 80 ]
}

Brute force seems not possible because the real problem can contain up to 1500 students.

Upvotes: 0

Views: 90

Answers (1)

aropan
aropan

Reputation: 636

I think you could use simulated annealing to find some optimal solution and use iou for metric.

I try to do it and not a perfect solution (mean IOU is equal to 0.8079440721):

{'G1': '2B', 'G2': '1B', 'G3': '1A', 'G4': '1B', 'G5': '1B', 'G6': '2B', 'G7': '1B', 'G8': '1B', 'G9': '2A', 'G10': '1A', 'G11': '1B', 'G12': '1B', 'G13': '2A', 'G14': '1A', 'G15': '1A', 'G16': '1B', 'G17': '1B', 'G18': '2B', 'G19': '1A', 'G20': '2A', 'G21': '2A', 'G22': '2B', 'G23': '1A', 'G24': '2B', 'G25': '2A', 'G26': '2B', 'G27': '2B', 'G28': '1B', 'G29': '2B', 'G30': '1A', 'G31': '1A'}

1B {'2': 2, '3': 12, '4': 9, '5': 1, '6': 71}
1A {'1': 5, '2': 17, '3': 30, '4': 12, '5': 1, '6': 16}
2B {'1': 6, '2': 9, '3': 16, '4': 30, '5': 10, '6': 43}
2A {'1': 8, '2': 12, '3': 36, '4': 7, '5': 1, '6': 16}

iou for 1B = 0.8571428571428571
iou for 1A = 0.75
iou for 2B = 0.8064516129032258
iou for 2A = 0.8181818181818182

Upvotes: 1

Related Questions