Создать группы без повторения предыдущих группировок

Question

Я создал случайного создателя группы, но случайный не гарантирует, что вы работаете с людьми, с которыми вы ранее не работали. Если кто-то смог создать «Генератор случайных групп с историей», который отслеживал предыдущие группы и избегал добавлять людей в группы с одними и теми же людьми снова и снова, я бы определенно использовал его! Кто-нибудь знает как это сделать?

Для ясности: Учитывая массив строк

["Jason", "Kim", "Callie", "Luke"] 

и массив предыдущих спариваний (также массивы)

[[["Jason", "Kim"], ["Callie", "Luke"]], [["Jason", "Luke"], ["Callie", "Kim"]]] 

обратные группировки с наименьшим количеством членов группы повторных

[["Jason", "Callie"], ["Luke", "Kim"]] 

Я представляю, что число, которое я пытаюсь свести к минимуму, - это количество повторных партиций ERS. Поэтому для каждой пары из двух человек, каждый раз, когда они уже были в команде, если результат помещает их в одну команду, результат будет иметь такой же результат. Для Например, «скоринг» прибыть на возвращаемое значение может выглядеть следующим образом:

["Jason", "Kim"] have a score of 1, they have been paired together before 
["Callie", "Luke"] have a score of 1, they have been paired together before 
["Jason", "Luke"] have a score of 1, they have been paired together before 
["Callie", "Kim"] have a score of 1, they have been paired together before 
["Jason", "Callie"] have a score of 0, they have not been paired together before 
["Luke", "Kim"] have a score of 0, they have not been paired together before 

Выберите наборы, которые охватывают весь список, генерируя наименьший балл. В этом случае пары [«Jason», «Callie»] и [«Luke», «Kim»] охватывают весь набор и имеют оценку 0 (без повторных группировок) и, следовательно, это оптимальное решение (0 являющийся наилучшим возможным результатом).

Возможно, это неправильный способ сделать это (поскольку я предполагаю, что это займет n квадратов), но, надеюсь, это дает представление о том, для чего я пытаюсь оптимизировать. Это не должно быть идеальной оптимизацией, просто «достойный ответ», который не объединяет одни и те же группы каждый раз.

В идеале, он сможет обрабатывать любую группу размеров, а также иметь возможность справиться с тем, что кто-то может быть в тот день (не все люди будут во всех массивах). Мне бы очень понравился javascript-ответ, но я мог бы перевести, если кто-то может придумать логику.

Answer 1

Вы можете собрать все пары в объекте и подсчитать. Затем возьмите только те, у которых меньше счетчик.

function getKey(array) { 
 
    return array.slice().sort().join('|'); 
 
} 
 

 
var strings = ["Jason", "Kim", "Callie", "Luke"], 
 
    data = [[["Jason", "Kim"], ["Callie", "Luke"]], [["Jason", "Luke"], ["Callie", "Kim"]]], 
 
    object = {}, 
 
    i, j, 
 
    keys; 
 

 
for (i = 0; i < strings.length - 1; i++) { 
 
    for (j = i + 1; j < strings.length; j++) { 
 
     object[getKey([strings[i], strings[j]])] = 0; 
 
    } 
 
} 
 

 
data.forEach(function (a) { 
 
    a.forEach(function (b, i) { 
 
     object[getKey(b)]++; 
 
    }); 
 
}); 
 

 
keys = Object.keys(object).sort(function (a, b) { 
 
    return object[b] - object[a]; 
 
}); 
 

 
keys.forEach(function (k) { 
 
    console.log(k, object[k]); 
 
}); 
 

 
console.log(object);

.as-console-wrapper { max-height: 100% !important; top: 0; }