两组不同大小的成员必须相互见面（1v1，一次）

我最近一直在努力编写一种“速度约会风格”算法。 基本目标是让一个团体的每个成员（男性）在他们的桌子上与其他团体（女性）的每个成员会面一次。

条件是：

1. 表的数量等于女性的数量。
2. 每个男人被分配到一个女人坐着的桌子（1v1对话）。
3. 在下一轮比赛中，每个人都会换到另一张他之前没去过的桌子。
4. 如果这些组的大小不同，那么没有任何成员（男人或女人）必须连续两轮停顿 （缺少一个伙伴）。

当男性组的成员多于女性组，或者反之亦然时，会出现困难。

例：

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轮比赛，最后还是暂停了两轮或更多轮等等。

_{*截图中的名称是假的; 由Faker生成}

---

我在Javascript中的当前（非工作）尝试

我基本上有四个数组

1. 一群男人
2. 一群妇女
3. 该轮的可用表数组
4. 一群未满足的女人每人

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

  Start Round 

Answer 1

这里的主要问题是确保男性和女性都不会连续两次停顿。

为了确保不会发生这种情况，可以考虑在桌子和女人之间放置“暂停表”，直到你有足够的桌子来安排男人。 这意味着在基于0的表编号中，这些“暂停表”获得奇数位置索引。

当你把男人从一个桌子循环到下一个桌子时，永远不会有一个男人连续两次“暂停”，但他们会在回到他们第一次被分配到的桌子之前遇到每个女人。

使用这种方法，当男性比女性多两倍时，问题也很明显。 在这种情况下，一个人按顺序暂停两次是不可避免的。

当男性较少时，可以使用类似的技巧：女性可能永远不会单独进行一轮以上，因此在这种情况下，使用相同的方法引入虚拟男性（“暂停座位”）：将男性排成一排，并在这一排注入这些“假人”，所以他们最终得到奇数指数。 我将这个可能延伸的行称为“座位”。

如果你这样做，你将拥有与桌子一样多的座位，并且为每一轮产生分配变得微不足道：只需在桌子上循环座位：每一轮座位按顺序移动到下一张桌子，骑自行车回到最后一个表后的第一个表。

这是代码：

 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

您可以暂停填充数组，并首先保持相同的数组长度。 然后，您可以使用数组的叉积，在第一个数组上移位，并保留第二个数组的值。

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

Answer 3

你可以像这样创建一个数组表：

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

获得：

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

因此，你只需要重新组合夫妇“新生代的rencontres”

Answer 4

好的我喜欢这个问题。 我的方法将处理，直到一个组的大小是另一组的两倍。 没有人会连续两次等待。 我也很高兴有机会使用我的Array.prototype.rotate()方法。

好吧，代码是;

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