[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 83 KB, 550x543, 1526324330162.jpg [View same] [iqdb] [saucenao] [google]
10154284 No.10154284 [Reply] [Original]

Hey,
Am in the process of making software to assign individuals to groups in accordance to belbin role theory.
Basically every group wants at least one representation of each role(9 roles total). Have been looking into combinatorics and optimization, but unable to solve my problem. (Want to find the most efficient way to find optimal groups)
It's not necessary that each role is represented in a group, but as many as possible.
Also, one person has 3 roles they can perform.

>> No.10154296
File: 240 KB, 1920x1080, 1541976149984.jpg [View same] [iqdb] [saucenao] [google]
10154296

Oh and my question is if anybody knows what sort of problem this is, and where I can read about it.

>> No.10154303

>>10154284
what is your definition of most efficient or optimal? Is it assigning the individual to the most number of groups or is it something else?
maybe try looking at bin-packing or knapsack problems and try to tweak them?

>> No.10154309

>>10154303
A person can only be assigned to one group. I think for example taking each individual and looking at each group to see if the role is missing and assigning to a group with 0 or lowest amount of representation of the role would result in a O(n^2) algoritm.

Granted beforehand is the amount of student (e.g. in a class) and the group sizes(e.g. 6 groups of 4 students each)

>> No.10154328

>>10154309
I still have no fucking clue what you're asking.
>every group wants at least one representation of each role
>it's not necessary that each role is represented in a group
>no definition of optimal group

Also, from what you're saying with your example, your complexity is O(nk) where k is the number of groups

>> No.10154341
File: 61 KB, 500x489, mock-their-laugh.jpg [View same] [iqdb] [saucenao] [google]
10154341

>>10154328
Shit, your right.
Also to define optimal, suppose a group gets a score out of 9 depending on how many roles are represented. 1 being the lowest (all same roles) and 9 being all roles represented.
The optimal case is the combination with highest mean average score of all the groups. Sorry if I'm still unclear.

>> No.10154366

>>10154341
I think O(nk) is the best you can do in this situation

>> No.10154491

The tricky part is that if you assign a person to a group as one of the three roles, it ends up "removing" the two other roles the person has

>> No.10155815

Random braindrops: What type of problem? A matching problem. You match groups against individuals. Game theory has figured matching out in many cases.

Also I think a greedy algorithm should do well; simple trick: First assign the individuals with the most common combination of roles. I have a hunch this might be optimal. I dont think this is NP. (Groups are alle being the same, individuals with the same attributes being the same, not many constraints). Might be wrong tho and a reduction to i.e. subset sum might lure somehwere.