I have 149 groups composed of individuals from a list of ~250. The grouping (tribe) composition is fixed, meaning the 3 members of each group cannot be switched. I need to create a schedule (6 days total) that will distribute the 149 groups into 25 groups per day, except the last day, with the condition that no single individual should have more than 1 occurrence per day.
Here is a copy of my dataset with dummy names.
Here is my Google Apps Script code so far:
var ui = SpreadsheetApp.getUi();
var sht = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('Tribes');
var schedSht = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('Schedule');
var nameSht = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('Names');
var tribesArr = sht.getRange(2, 1, sht.getLastRow() - 1, 1).getValues();
var tribesOrder = tribesArr.map(function(t) { return t[0] });
tribesArr = tribesArr.map(function(t) { return t[0] });
var tribes = randomize(tribesArr);
var takenTribes = [];
var tribeSet = [];
var nameSet = [];
var LastDayTribeNum = 24;
var otherDaysTribeNum = 25;
var numDays = 6;
function makeMenu() {
ui.createMenu('My Menu').addItem('Create Randomized Schedule', 'makeSchedule').addToUi();
}
function makeSchedule() {
var dayNum = 1;
while (dayNum < numDays + 1) {
var remainingTribes = tribes.filter(function(r) { return takenTribes.indexOf(r) < 0; });
var daySched = fillUpDay(dayNum, remainingTribes);
tribeSet.push(daySched.tribes);
nameSet.push(daySched.names);
dayNum++;
}
remainingTribes = tribes.filter(function(r) { return takenTribes.indexOf(r) < 0; });
if (takenTribes.length < tribes.length) {
remainingTribes.forEach(swap);
}
tribeSet.forEach(function(tribe) {
schedSht.appendRow(tribe);
});
nameSet.forEach(function(name) {
nameSht.appendRow(name);
});
}
function fillUpDay(revDay, remTribes) {
var sched = {};
var namesToday = [];
var tribesToday = [];
var currIdx = 0;
var tribeMaxNum = (revDay === numDays) ? LastDayTribeNum : otherDaysTribeNum;
while (tribesToday.length < tribeMaxNum && currIdx < remTribes.length) {
var row = tribesOrder.indexOf(remTribes[currIdx]) + 2;
var currNames = sht.getRange(row, 2, 1, 3).getValues()[0];
var nameFound = false;
//check if name of tribe already in today's list
for (var t = 0; t < 3; t++) {
if (namesToday.indexOf(currNames[t]) !== -1) {
nameFound = true;
}
}
if (!nameFound) {
//if names of all three not in the list, add all three to today's list and remove tribe from list of unscheduled tribes
namesToday = namesToday.concat(currNames);
tribesToday.push(remTribes[currIdx]);
takenTribes.push(remTribes[currIdx]);
currIdx++;
} else {
//go to next tribe
currIdx++;
}
}
sched.tribes = tribesToday;
sched.names = namesToday;
return sched;
}
function swap(tribeToSwap) {
var row = tribesOrder.indexOf(tribeToSwap) + 2;
var namesInTribe = sht.getRange(row, 2, 1, 3).getValues()[0];
var len = nameSet.length;
var idx = 0;
var found = checkInSet(namesInTribe, nameSet[idx]);
var swapped = false;
while (!swapped && idx < len - 1) {
if (!found) {
// try swap
var tempNameArr = nameSet[idx];
tempNameArr.slice(3);
tempNameArr.push(namesInTribe);
var removedNames = nameSet[idx];
removedNames.slice(0, 3);
var lastNames = nameSet[len - 1];
var good = true;
for (var c = 0; c < 3; c++) {
if (lastNames.indexOf(removedNames[c]) > -1) {
good = false;
}
}
if (good) {
// swap
tribeSet[idx].slice(1);
nameSet[idx] = tempNameArr;
tribeSet[len - 1].push(tribeToSwap);
nameSet[len - 1].push(removedNames);
swapped = true;
}
} else {
// try next day
idx++;
found = checkInSet(namesInTribe, nameSet[idx]);
}
}
}
function checkInSet(names, setNames) {
var found = false;
for (var idx = 0; idx < names.length; idx++) {
if (setNames.indexOf(names[idx]) > -1) {
found = true;
}
}
return found;
}
function randomize(array) {
//https://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
var currentIndex = array.length,
temporaryValue, randomIndex;
while (0 !== currentIndex) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
What I did was to create an array per day and check if a member of the current index's corresponding group (tribe) exists in the day's names array, and move on to the next index if found until the quota for the day (25) is reached. If names are not found for the day, the tribe will be marked as taken and will no longer be included in the subsequent schedules. Results will be appended to their respective sheets. If there are tribes that weren't matched because a name already appears for that day, I try to swap it in another day.
The code runs most of the time (gets completed in ~5s). Some other times, it runs for minutes that I cancel it. BUT, I never get what I need in any run. I will get 149 tribes in the Schedule sheet, but when I check the names, I don't get 447 names (with no repetition per day). I can't pinpoint where to adjust the algorithm. I hope someone can at least give hints, and better, a solution. Pardon the messy code.
Aucun commentaire:
Enregistrer un commentaire