草庐IT

javascript - 两组大小不同的成员必须相遇(1v1,一次)

coder 2024-05-10 原文

我最近一直在努力编写一种“快速约会风格”算法。基本目标是让一组(男性)的每个成员在他们的 table 上与另一组(女性)的每个成员见面一次。

条件是:

  1. table 数与女性人数相同。
  2. 每个男人都被分配到一张 table , table 上有一个女人坐着(1v1 对话)。
  3. 在下一轮中,每个人都被切换到他之前没有去过的另一张 table 。
  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 轮,结果仍然有人暂停 2 轮或更多轮,等等。

* 截图中的名字是假的;由 Faker 生成


我目前在 Javascript 中的(非工作)尝试

我基本上有四个数组

  1. 一群人
  2. 一群女人
  3. 本轮可用牌 table 的数组
  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>

最佳答案

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

为确保这种情况不会发生,请考虑在女性 table 之间放置“暂停 table ”,直到您有足够的 table 让男性就座。这意味着在基于 0 的表编号中,这些“暂停表”获得奇数位置索引。

然后当您将男人从一张 table 循环到另一张 table 时,永远不会有男人连续两次“暂停”,但他们会在回到第一张 table 之前遇到每个女人分配给。

通过这种方法,当男性人数是女性人数的两倍多时,显然没有解决问题的方法。在那种情况下,一个人连续两次暂停是不可避免的。

当男性人数较少时,可以使用类似的技巧:女性可能永远不会连续超过一轮,因此在这种情况下,使用相同的方法引入虚拟男性(“暂停座位”):将男性放在一行,并在这一行中注入(inject)这些“虚拟人”,因此它们最终会出现奇数索引。我将这个可能扩展的行称为“座位”。

如果您执行上述操作,您将拥有与 table 一样多的座位,并且为每一轮生成分配变得微不足道:只需在 table 上循环座位:每一轮一个座位移动到下一张 table 顺序,在最后一张 table 后循环回到第一张 table 。

代码如下:

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

关于javascript - 两组大小不同的成员必须相遇(1v1,一次),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39189112/

有关javascript - 两组大小不同的成员必须相遇(1v1,一次)的更多相关文章

  1. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入,例如“100兆字节”或“1GB”,并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前,我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效,但前提是输入是倍数(“gigabytes”,而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以,功能正常,

  2. ruby - 使用 Vim Rails,您可以创建一个新的迁移文件并一次性打开它吗? - 2

    使用带有Rails插件的vim,您可以创建一个迁移文件,然后一次性打开该文件吗?textmate也可以这样吗? 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件,这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails,您可以创建一个新的迁移文件并一次性打开它吗?,我们在StackOverflow上找到一个类似的问题: https://sta

  3. ruby - 如何每月在 Heroku 运行一次 Scheduler 插件? - 2

    在选择我想要运行操作的频率时,唯一的选项是“每天”、“每小时”和“每10分钟”。谢谢!我想为我的Rails3.1应用程序运行调度程序。 最佳答案 这不是一个优雅的解决方案,但您可以安排它每天运行,并在实际开始工作之前检查日期是否为当月的第一天。 关于ruby-如何每月在Heroku运行一次Scheduler插件?,我们在StackOverflow上找到一个类似的问题: https://stackoverflow.com/questions/8692687/

  4. ruby-on-rails - Rails 模型——非持久类成员或属性? - 2

    对于Rails模型,是否可以/建议让一个类的成员不持久保存到数据库中?我想将用户最后选择的类型存储在session变量中。由于我无法从我的模型中设置session变量,我想将值存储在一个“虚拟”类成员中,该成员只是将值传递回Controller。你能有这样的类(class)成员吗? 最佳答案 将非持久属性添加到Rails模型就像任何其他Ruby类一样:classUser扩展解释:在Ruby中,所有实例变量都是私有(private)的,不需要在赋值前定义。attr_accessor创建一个setter和getter方法:classUs

  5. ruby-on-rails - ActionController::RoutingError: 未初始化常量 Api::V1::ApiController - 2

    我有用于控制用户任务的Rails5API项目,我有以下错误,但并非总是针对相同的Controller和路由。ActionController::RoutingError:uninitializedconstantApi::V1::ApiController我向您描述了一些我的项目,以更详细地解释错误。应用结构路线scopemodule:'api'donamespace:v1do#=>Loginroutesscopemodule:'login'domatch'login',to:'sessions#login',as:'login',via::postend#=>Teamroutessc

  6. HBase Region 简介和建议数量&大小 - 2

    Region是HBase数据管理的基本单位,region有一点像关系型数据的分区。region中存储这用户的真实数据,而为了管理这些数据,HBase使用了RegionSever来管理region。Region的结构hbaseregion的大小设置默认情况下,每个Table起初只有一个Region,随着数据的不断写入,Region会自动进行拆分。刚拆分时,两个子Region都位于当前的RegionServer,但处于负载均衡的考虑,HMaster有可能会将某个Region转移给其他的RegionServer。RegionSplit时机:当1个region中的某个Store下所有StoreFile

  7. java - 为什么 ruby​​ modulo 与 java/other lang 不同? - 2

    我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生,2个-22个-2但在Ruby中,相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个?模块操作在Ruby中是如何实现的?如果将同一个操作定义为一个web服务,两个服务如何匹配逻辑。 最佳答案 在Java中,模运算的结果与被除数的符号相同。在Ruby中,它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.

  8. ruby-on-rails - Rake 任务仅调用一次时执行两次 - 2

    我写了一个非常简单的rake任务来尝试找到这个问题的根源。namespace:foodotaskbar::environmentdoputs'RUNNING'endend当在控制台中执行rakefoo:bar时,输出为:RUNNINGRUNNING当我执行任何rake任务时会发生这种情况。有没有人遇到过这样的事情?编辑上面的rake任务就是写在那个.rake文件中的所有内容。这是当前正在使用的Rakefile。requireFile.expand_path('../config/application',__FILE__)OurApp::Application.load_tasks这里

  9. ruby-on-rails - 在 RSpec 中,如何以任意顺序期望具有不同参数的多条消息? - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的,所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法,用allowstub,除了方法名称之外没有任何约束,调用该方法,然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  10. ruby-on-rails - Ruby 中意外的大小写行为 - 2

    我在一段非常简单的代码(如我所想)中得到了一个错误的值:org=4caseorgwhenorg=4val='H'endputsval=>nil请不要生气,我希望我错过了一些非常明显的东西,但我真的想不通。谢谢。 最佳答案 这是典型的Ruby错误。case有两种被调用的方法,一种是你传递一个东西作为分支的基础,另一种是你不传递的东西。如果您确实在case中指定了一个表达式语句然后评估所有其他条件并与===进行比较.在这种情况下org评估为false和org===false显然不是真的。所有其他情况也是如此,它们要么是真的,要么是假的。

随机推荐