Skip to content

Instantly share code, notes, and snippets.

@mickadoo
Last active June 7, 2017 06:41
Show Gist options
  • Save mickadoo/74da6a944201b6bf53a58e03c576b1a7 to your computer and use it in GitHub Desktop.
Save mickadoo/74da6a944201b6bf53a58e03c576b1a7 to your computer and use it in GitHub Desktop.
Sort a dataset of school IDs and group IDs into pairs of the same group, but where school ID must be different
<?php
$pairs = [];
$dataSet = [];
const SCHOOL_ID_COL = 0;
const GROUP_ID_COL = 1;
// load data
$fileName = __DIR__ . '/matching_problem.csv';
$fileHandle = fopen($fileName, 'r');
while (($row = fgetcsv($fileHandle)) !== FALSE) {
$dataSet[] = [$row[0], $row[1]];
}
fclose($fileHandle);
if (!is_numeric($dataSet[0][SCHOOL_ID_COL])) {
unset($dataSet[0]);
}
// sort by order of school ID frequency
$schoolFreq = array_count_values(array_column($dataSet, SCHOOL_ID_COL));
arsort($schoolFreq);
$schoolFreq = array_keys($schoolFreq);
$sortedDataSet = [];
foreach ($schoolFreq as $schoolId) {
foreach ($dataSet as $student) {
if ($student[SCHOOL_ID_COL] == $schoolId) {
$sortedDataSet[] = $student;
}
}
}
$dataSet = $sortedDataSet;
// loop through all groups and find pairs
$groupIds = array_unique(array_column($dataSet, GROUP_ID_COL));
foreach ($groupIds as $groupId) {
while (!is_null($firstKey = getNextStudent($dataSet, $groupId))
&& ($schoolId = $dataSet[$firstKey][SCHOOL_ID_COL])
&& !is_null($secondKey = getNextStudent($dataSet, $groupId, $schoolId))
) {
$pairs[] = [$dataSet[$firstKey], $dataSet[$secondKey]];
unset($dataSet[$firstKey], $dataSet[$secondKey]);
}
}
printf('made %d pairs', count($pairs));
function getNextStudent($dataSet, $groupId, $excludeSchool = NULL) {
foreach ($dataSet as $key => $student) {
$groupMatch = $student[GROUP_ID_COL] == $groupId;
$schoolId = $student[SCHOOL_ID_COL];
$isAllowed = !$excludeSchool || $schoolId != $excludeSchool;
if ($groupMatch && $isAllowed) {
return $key;
}
}
return NULL;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment