Skip to content

Instantly share code, notes, and snippets.

@korymath korymath/partition.py
Last active Apr 16, 2018

Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.