Members of two groups of different size must meet

Question

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.

_{* 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 1

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);

Answer 2

OK I loved this question. My approach will handle up until a group is twice the size of the other. Nobody will wait twice in a row. I am also happy to take the chance to use my Array.prototype.rotate() method as well.

Well ok the code is;

Array.prototype.rotate = function(n){
	var len = this.length,
	    res = new Array(this.length);
	if (n % len === 0) return this.slice(); // no need to rotate just return a copy
	else for (var i = 0; i < len; i++) res[i] = this[(i + (len + n % len)) % len];
	return res;
};

function arrangeTables(matches){
  var meetings = [],
    tableCount = matches[0].length;
  for (var i = 0, len = matches.length; i < len; i++){
    meetings.push(matches.slice(0,tableCount).map((t,ix) => t[ix]));
    matches = matches.concat(matches.splice(0,tableCount).rotate(1));
  }
  return meetings;
}

var men = ['m1', 'm2', 'm3', 'm4', 'm5'],
  women = ['w1', 'w2', 'w3'],
    few = [],
   much = men.length > women.length ? (few = women,men) : (few = men,women), // this is needed for the nesting order of maps to get matches.
matches = much.map(m => few.map(f => [f,m]));
 result = arrangeTables(matches);
console.log(result);

Well we have gender in short many tables for each round and we have to make as many rounds as the number of gender in excess.

First we find all possible matches

matches = much.map(m => few.map(f => [f,m]))

which return us

[ [ [ 'w1', 'm1' ], [ 'w2', 'm1' ], [ 'w3', 'm1' ] ],
  [ [ 'w1', 'm2' ], [ 'w2', 'm2' ], [ 'w3', 'm2' ] ],
  [ [ 'w1', 'm3' ], [ 'w2', 'm3' ], [ 'w3', 'm3' ] ],
  [ [ 'w1', 'm4' ], [ 'w2', 'm4' ], [ 'w3', 'm4' ] ],
  [ [ 'w1', 'm5' ], [ 'w2', 'm5' ], [ 'w3', 'm5' ] ] ]

then we move to our arrangeTables() function. It works like this

1. Take first table many rows (3 in this case) and pick 3 meetings according to the row index and put them in an array.

   meetings.push(matches.slice(0,tableCount).map((t,ix) => t[ix]));

   So [["w1","m1"],["w2","m2"],["w3","m3"]] are picked in the first round.

2. Remove the first three rows of matches. Rotate the removed rows once and concatenate them back to the matches.

   matches = matches.concat(matches.splice(0,tableCount).rotate(1));

   So the matches would become as follows in the second round.

   [ [ [ 'w1', 'm4' ], [ 'w2', 'm4' ], [ 'w3', 'm4' ] ],
     [ [ 'w1', 'm5' ], [ 'w2', 'm5' ], [ 'w3', 'm5' ] ],
     [ [ 'w1', 'm2' ], [ 'w2', 'm2' ], [ 'w3', 'm2' ] ],
     [ [ 'w1', 'm3' ], [ 'w2', 'm3' ], [ 'w3', 'm3' ] ],
     [ [ 'w1', 'm1' ], [ 'w2', 'm1' ], [ 'w3', 'm1' ] ] ]
   

3. And repeat this routine "number of gender in excess" many times. (5 in this case)

Answer 3

You could just create an array tables like this :

var tables = men.map((element, index) => index < women.length ? [element, women[index]] : [element, "pause"]);

To obtain :

[ [ 'm1', 'w1' ],
  [ 'm2', 'w2' ],
  [ 'm3', 'w3' ],
  [ 'm4', 'pause' ],
  [ 'm5', 'pause' ] 
]

Hence you would just have to recombinate couples for "nouvelles rencontres"

Answer 4

You could fill the arrays with pause and maintain the same length of the arrays, first. Then you could use the cross product of the arrays with a shift on the first array and by keeping the value of the second array.

function getSeating(a1, a2) {
    function fill(a, l) {
        var p = l - a.length;
        a = a.slice();
        while (p) {
            a.splice(p, 0, 'pause' + p);
            p--;
        }
        return a;
    }

    var max = Math.max(a2.length, a1.length);

    a1 = fill(a1, max);
    a2 = fill(a2, max);
    return a1.map(function (_, i) {
        return a2.map(function (b, j) {
            return [a1[(i + j) % max], b];
        });
    });
}

console.log(getSeating(['m1', 'm2', 'm3', 'm4', 'm5'], ['w1', 'w2', 'w3']));
console.log(getSeating(['m1', 'm2', 'm3'], ['w1', 'w2', 'w3', 'w4', 'w5']));
console.log(getSeating(['m1', 'm2', 'm3', 'm4', 'm5'], ['w1', 'w2', 'w3', 'w4', 'w5']));

console.log(getSeating(['m1', 'm2', 'm3', 'm4'], ['w1', 'w2']));
console.log(getSeating(['m1', 'm2'], ['w1', 'w2', 'w3', 'w4']));
console.log(getSeating(['m1', 'm2', 'm3', 'm4'], ['w1', 'w2', 'w3', 'w4']));

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