两组不同大小的成员必须相互见面(1v1,一次)

Question

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

条件是:

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

当Men组的成员多于Women组时会出现困难,反之亦然.

例:

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中的当前(非工作)尝试

我基本上有四个数组

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

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

为了确保这种情况不会发生，可以考虑在女性桌子之间放置“暂停桌”，直到有足够的桌子容纳男性。这意味着在基于 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);