Francisco H. Francisco H. - 3 months ago 7
jQuery Question

Members of two groups of different size must meet each other (1v1, once)

I've been struggling recently writing a kind of "speed dating style" algorithm. The basic goal is for each member of one group (Men) to meet each member of the other group (Women) at their table, once.

The conditions are:


  1. The number of tables are equal to the number of women.

  2. Each man is assigned to a table where a woman is sitting (1v1 dialogue).

  3. In the next round, each man is switched to another table he has not been to before.

  4. If the groups are of different size, no member (man or woman) must be in pause (lack a partner) for two rounds in a row.



Difficulty arises when the Men group has more members than the Women group, or vice-versa.

Example:

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 │
└───────────────────────────┘


Matchups therefore are:

var results = [
'm1' = [
'w1', 'w3', null
],

'm2' = [
'w2', null, 'w1'
],

'm3' = [
'w3', null, 'w2'
],

'm4' = [
null, 'w1', 'w3'
],

'm5' = [
null, 'w2', null
],
];


So far my attempts at tackling this problem have been unsuccessful, despite looking at similar questions in this site and others (see screenshot below). In this attempt I ran 15/15 rounds and still ended up with persons in pause for 2 or more rounds, etc.

enter image description here
* Names in the screenshot are fake; generated by Faker




My current (non-working) attempt in Javascript



I basically have four arrays


  1. Array of men

  2. Array of women

  3. Array of available tables for the round

  4. Array of unmet women per man





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>




Answer

The main problem here is making sure neither men nor women are put on pause twice in a row.

To ensure this does not happen, think of placing "pause tables" in between the tables with the women, until you have enough tables to seat the men. This means in a 0-based table numbering, that these "pause tables" get an odd position index.

When you then cycle the men from one table to the next, there will never be a man that is put on "pause" twice in a row, yet they will meet every woman before they get back to the table they were first assigned to.

With this method it also becomes apparent that there is no solution to the problem when there are more than twice as many men as women. In that case it is unavoidable that a man is put on pause twice in sequence.

A similar trick can be used when there are fewer men: women may never be alone for more than one round in sequence, so in this case introduce dummy men ("pause seaters") with the same methodology: put the men in a row, and inject in this row these "dummy men" so they end up at odd indices. I call this potentially extended row the "seaters".

If you do the above, you'll have just as many seaters as tables, and it becomes trivial to produce the assignments for each round: just cycle the seaters over the tables: each round a seater moves to the next table in sequence, cycling back to the first table after the last one.

Here is the code:

function getRounds(men, women) {
    // Exclude the cases where a solution is not possible
    if (men.length > women.length * 2) throw "not possible: too many men"; 
    if (women.length > men.length * 2) throw "not possible: too many women"; 
    // Create the tables:
    // Women get a fixed place, so the table name is the woman's name
    var tables = women.slice();
    // Create the seaters: they are the men
    var seaters = men.slice();
    // Which do we have fewer of? tables or seaters?
    var maxLen = Math.max(tables.length, seaters.length);
    var least = tables.length < maxLen ? tables : seaters;
    // The smallest of both arrays should get some dummies added to it.
    // We insert the dummies at odd indices: This is the main point of this algorithm
    for (var i = 0; least.length < maxLen; i++) least.splice(i*2+1, 0, 'pause');

    // Now everything is ready to produce the rounds. There are just as many
    // rounds as there are tables (including the "pause tables"):
    return tables.map( (_, round) =>    
        // Assign the men: each round shifted one place to the left (cycling):
        tables.map( (table, tid) => [seaters[(round+tid)%maxLen], table] )
    );
}

var result1 = getRounds(["John", "Tim", "Bob", "Alan", "Fred"], 
                        ["Lucy", "Sarah", "Helen"]);
console.log(result1);

var result2 = getRounds(["John", "Tim"],
                        ["Lucy", "Sarah", "Helen", "Joy"]);
console.log(result2);