Split a group of people in half based on preference

Question

I'm a 3d Animation Tutor with very basic Python knowledge and have been bashing my head against a wall trying to code what I think could be a VERY beneficial script.. Any help would, including a simple point in the right direction would be very much appreciated. Thanks in advance.

Here is my scenario: My class of 18 students is about to enter into the "group project" module. This year I would like to split the class in half to keep the projects more manageable and also to encourage healthy competition. The students have already filled out surveys in which they annotated their preference for working with all the other students by giving each a number between 0 and 5. My idea is that I can use these surveys to mathematically calculate the best possible split in terms of preference.

Now I've made a very basic start in CodeSkulptor - a browser based python emulator. In this prototype version I am starting with just 4 sample "students" - A, B, C and D. Each student has given their opinions of the others and to keep things simple, their opinion of themselves is all set at 0, (though this could just as easily be any value, since you can't NOT work with yourself..)

Here is my psuedocode:

1. Create empty set "students" that will contain all students, i.e. [A,B,C,D]

2. Create an empty set "combinations" that will be filled with all of the possible combinations, i.e [((A,B),(C,D)),((A,C),(B,D)),((A,D)(B,C))]

3. define a class containing preference information for each student, once all the possible combinations have been determined, this information will be used to calculate the combination with the overall highest "Happiness"/"Morale"..

4. Create a function that cycles through all the possible combinations, returning them as lists of lists which get added to the combinations set.

5. ( Not added yet ) Create a function that cycles through all the combinations in the set "combinations", and calculates overall "happiness" based off the preferences stored in the student class.

6. ( Not added yet ) Create a function that prints the combinations with the highest happiness.

In this case it should print:

print"A,B/C,D = 7"

print"A,C/B,D = 10"

print"A,D/B,C = 15"

print"Highest possible split is A,D/B,C with overall happiness of 15!"

I'm kind of embarrassed to show the WIP.. but here it is:

http://www.codeskulptor.org/#user17_EEvOfHGg7AAZt1w_1.py

Or for those that would rather stay on this page:

people = set([])
combinations = set([])

class person:
    def __init__(self, name, A = 3, B = 3, C = 3, D = 3):
        self.name = name
        self.A = A
        self.B = B
        self.C = C
        self.D = D

    def get_name(self):
        return self.name

    def get_A(self):
        return self.A

    def get_B(self):
        return self.B

    def get_C(self):
        return self.C

    def get_D(self):
        return self.D    

# make all the possible combinations
#def combine(people):
#combine any 2 given people into a new group

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

####[A,B,C,D]
people.add(person("A", 0, 1, 2, 4))
people.add(person("B", 3, 0, 3, 4))
people.add(person("C", 1, 5, 0, 2))
people.add(person("D", 3, 3, 2, 0))

combinations(people,2)

The combinations function - I actually lifted straight off the itertools documentation page, but I'm not exactly sure if it's working or even if this is the best way to split the groups. I can't import itertools directly as CodeSkulptor only supports a few modules (math, random, time etc.). I tried using actual python but it functions a whole lot differently than I'm used to. I have learned many things in my research, such as that calculating something like this may take years for the computer to go through the 24310 different split possibilities.. Another option would be for the code to just generate 100 random split possibilities at a time and I could keep track of the highest result each runthrough. All in all, it's been a fun script to try and figure out - actually a little too fun. I can't physically tear myself away from it, even though I've stopped making actual progress. So please, if someone could hint/show me where to go from here I would very much appreciate the help.

Cheers,

• Eli

Answer 1

Completed

from itertools import combinations
import numpy as np
import string

    def get_maxhappiness(results):
        max_happiness = max(results)
        index = results.index(max_happiness)
    
        #Printing the result! (There may be more than one best result, but this will only show 1)
        print "Optimal Groups: Point value of",max_happiness,"\n",groups[index],"\n", anti_groups[index]
        results[index] = 0
        return results

def calculateHappiness(points,group):
    happiness = 0
    for i in range(len(group)):
        person_prefs = points[group[i]]
        others = group[i:] + group[:i]
        for other in others:
            happiness += person_prefs[other]
    return happiness



if __name__ == "__main__":
    people = string.letters[26:44]
    groups = list(combinations(people,9))
    anti_groups = [tuple(set(people).difference(set(x))) for x in groups]

    #Making fake results
    survey_results = dict()
    for person in people:
        results = dict(zip(people,np.random.randint(0,10,size=(len(people)))))
        results[person] = 0
        survey_results[person] = results

    #Printing Survey Results
    for name,values in survey_results.items():
        print "Student:", name, "has preferences:", values

    #Calculating happiness for every group
    results = []
    for i in range(len(groups)):
        results.append(calculateHappiness(survey_results,groups[i])+calculateHappiness(survey_results,anti_groups[i]))
    #Finding the largest happiness value
    top_n = 5
    while top_n > 0:
        results = get_maxhappiness(results)
        top_n -= 1

Yields:

...

Student: N has preferences: {'A': 5, 'C': 5, 'B': 0, 'E': 0, 'D': 3, 'G': 6, 'F'
: 8, 'I': 8, 'H': 3, 'K': 1, 'J': 4, 'M': 4, 'L': 9, 'O': 0, 'N': 0, 'Q': 3, 'P'
: 2, 'R': 2}
Student: Q has preferences: {'A': 9, 'C': 0, 'B': 3, 'E': 4, 'D': 3, 'G': 2, 'F'
: 2, 'I': 7, 'H': 5, 'K': 2, 'J': 3, 'M': 0, 'L': 9, 'O': 2, 'N': 5, 'Q': 0, 'P'
: 2, 'R': 0}
Student: P has preferences: {'A': 2, 'C': 3, 'B': 0, 'E': 9, 'D': 3, 'G': 6, 'F'
: 7, 'I': 1, 'H': 7, 'K': 9, 'J': 7, 'M': 4, 'L': 8, 'O': 2, 'N': 6, 'Q': 5, 'P'
: 0, 'R': 7}
Student: R has preferences: {'A': 5, 'C': 3, 'B': 7, 'E': 1, 'D': 5, 'G': 6, 'F'
: 1, 'I': 6, 'H': 9, 'K': 9, 'J': 3, 'M': 6, 'L': 8, 'O': 8, 'N': 5, 'Q': 1, 'P'
: 3, 'R': 0}
Optimal Groups: Point value of 709
('A', 'B', 'F', 'G', 'J', 'K', 'O', 'Q', 'R')
('C', 'E', 'D', 'I', 'H', 'M', 'L', 'N', 'P')
(x4)