Недавно я боролся с написанием своего рода алгоритма "стиль знакомства с сайтом". Основная цель состоит в том, чтобы каждый член одной группы (Мужчины) встречался с каждым членом другой группы (Женщины) за их столом один раз.
Условия:
- Количество таблиц равно количеству женщин.
- Каждому человеку присваивается таблица, где сидит женщина (диалог 1v1).
- В следующем раунде каждый человек переключается на другую таблицу, в которой он не был раньше.
- Если группы имеют разный размер, ни один член (мужчина или женщина) не должен находиться в состоянии паузы (отсутствие партнера) в течение двух раундов подряд.
Сложность возникает, когда группа мужчин имеет больше членов, чем группа женщин, или наоборот.
Пример:
var men = [
'm1', 'm2', 'm3', 'm4', 'm5',
],
women = [
'w1', 'w2', 'w3'
];
┃ ROUND 1 ┃ ROUND 2
┌─────────────┬─────────────┐ ┌─────────────┬─────────────┐
│ men │ women │ │ men │ women │
├─────────────┴─────────────┤ ├─────────────┴─────────────┤
│ m1 >>> w1 │ │ m4 >>> w1 │
│ m2 >>> w2 │ │ m5 >>> w2 │
│ m3 >>> w3 │ │ m1 >>> w3 │
│ m4 pause │ │ m2 pause │
│ m5 pause │ │ m3 pause │
└───────────────────────────┘ └───────────────────────────┘
┃ ROUND 3
┌─────────────┬─────────────┐
│ men │ women │
├─────────────┴─────────────┤
│ m2 >>> w1 │
│ m3 >>> w2 │
│ m4 >>> w3 │
│ m5 pause │
│ m1 pause │
└───────────────────────────┘
Сопоставлениями являются:
var results = [
'm1' = [
'w1', 'w3', null
],
'm2' = [
'w2', null, 'w1'
],
'm3' = [
'w3', null, 'w2'
],
'm4' = [
null, 'w1', 'w3'
],
'm5' = [
null, 'w2', null
],
];
До сих пор мои попытки решить эту проблему были безуспешными, несмотря на то, что они рассматривали подобные вопросы на этом сайте и другие (см. снимок экрана ниже). В этой попытке я побежал 15/15 раундов и все еще получал людей в паузе на 2 или более раунда и т.д.
* Имена на скриншоте являются фальшивыми; созданный Faker
Моя текущая (нерабочая) попытка в Javascript
В основном я имею четыре массива
- Массив людей
- Массив женщин
- Массив доступных таблиц для раунда
- Массив неудовлетворенных женщин на человека
var men_array = [
'm1', 'm2', 'm3', 'm4', 'm5', 'm6', 'm7', 'm8', 'm9', 'm10'
];
var women_array = [
'w1', 'w2', 'w3', 'w4', 'w5'
];
var available_tables_this_round = [];
var unmet_women = [];
// Run round
function start_round(){
console.log('START OF ROUND ----------------');
// Set available tables this round
// One table per woman
available_tables_this_round = women_array;
// Selected table
var selected_table;
// Finding table partner for each man
men_array.forEach(function(item){
var current_man = item;
// Checking if this user has unmet women on record
if(typeof unmet_women[current_man] == 'undefined'){
// Unmet women array not set. Setting...
unmet_women[current_man] = women_array;
}
// Loop through available tables to see which
// of those the man can join (has not visited yet).
for(var i = 0; i < available_tables_this_round.length; i++){
var current_woman = available_tables_this_round[i];
// If woman among the available has not been met
if($.inArray(current_woman, available_tables_this_round) !== -1){
selected_table = current_woman;
// Removing table from those available this round
available_tables_this_round = $.grep(available_tables_this_round, function(value) {
return value != selected_table;
});
// Removing woman from unmet by this man
unmet_women[current_man] = $.grep(unmet_women[current_man], function(value) {
return value != selected_table;
});
console.log(current_man, '>>>', selected_table);
// Exiting loop since we've found a match for the man (for this round!)
break;
}
}
});
console.log('END OF ROUND ----------------');
}
// Button handling
$(document).on('click', 'button#start_round_btn', start_round);<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<button id="start_round_btn">Start Round</button>