partition.py

import random
import itertools
import numpy as np
from tqdm import tqdm

# 0) define the starting set
num_students = 20
student_ids = np.arange(num_students)
all_combinations = list(itertools.combinations(student_ids, 2))

# 1) shuffle
random.shuffle(x=student_ids)

# 2) partition
partitions = {}
partitions[0] = set(student_ids[:num_students/2])
print('Size of partition 0: {}'.format(len(partitions[0])))
partitions[1] = set(student_ids[num_students/2:])
print('Size of partition 1: {}'.format(len(partitions[1])))

# 2) define a multiple restart partitioning function
def multiple_restart_partitions(num_partition_restarts=6):
    # dictionary to collect all partition steps
    all_partition_steps = {}
    # perform multiple partition steps
    for i in range(num_partition_restarts):
        random.shuffle(x=student_ids)
        all_partition_steps[i] = {}
        all_partition_steps[i][0] = set(student_ids[:num_students/2])
        all_partition_steps[i][1] = set(student_ids[num_students/2:])
    
    # score the pairwise occurence
    pairwise_occurences = {}
    
    # for each unique combination of two students
    for student_pair in all_combinations:
        # define each student
        student_A = student_pair[0]
        student_B = student_pair[1]
        
        pair_key = '{}-{}'.format(student_A, student_B)
        
        # allocate a list for the pairwise occurence tracking
        pairwise_occurences[pair_key] = []
        
        # over all the partition steps
        for i, partition in enumerate(all_partition_steps.iteritems()):
            group_A = partition[1][0]
            group_B = partition[1][1]
            # if the combination of students are both in the first group
            if (student_A in group_A) and (student_B in group_A):
                pairwise_occurences[pair_key].append(i)
            # or if the combination of students are both in the second group
            elif (student_A in group_B) and (student_B in group_B):
                pairwise_occurences[pair_key].append(i)
            else:
                break
        
    total_pairwise_combos = 0
    num_keys = 0
    for k,v in pairwise_occurences.iteritems():
        total_pairwise_combos += len(v)
        num_keys += 1
            
    return all_partition_steps, pairwise_occurences, total_pairwise_combos, num_keys

# brute force a random search solution
min_pairwise_combos = 1000

for i in tqdm(range(1000)):
    random.seed(i)
    (all_partition_steps, 
     pairwise_occurences, 
     total_pairwise_combos,
     num_keys) = multiple_restart_partitions(num_partition_restarts=6)
    
    if total_pairwise_combos < min_pairwise_combos:
        best_partition_steps = all_partition_steps
        min_pairwise_combos = total_pairwise_combos
        
print('Number of unique combinations of two students: {}'.format(num_keys))
print('Total pairwise combinatons over partition: {}'.format(min_pairwise_combos))
print('\n Best partitions: \n')
print(all_partition_steps)