根据偏好列表分配组（以3为例）

-1

这是从纯粹的算法角度开始的问题的第三次迭代，现在已经变成绝望的任务来寻找我可以理解的代码示例。根据偏好列表分配组（以3为例）

我想要做的是创建g人群列表，试图满足尽可能多的偏好。每个人给出了排名前列的n列表中他们想要分配的其他人。它（我的程序）需要将相互请求视为单向的更有影响力，并且应该（希望）找到接近最佳解决方案的东西。

我想要某种代码示例（实际上是任何基于C的语言或详细的伪代码），以便我可以理解所需的算法并编写我的程序。在我的第一个问题之后，我已经确定这可能需要某种关于稳定婚姻问题的变体，但我一直无法找到伪代码或我能理解的实际语言的完整示例。

我已经询问了算法HERE和HERE前面的问题，但没有拿出任何东西（我认为这是由于这些SE论坛极低的用户数）。现在我在这里问一个问题，希望更高的观看率和一个面向程序设计的问题能够为我提供一个答案。

是的，我意识到这样的问题之前已经被问到过，但没有一个可以应用和回答。

有谁知道我该怎么做？

要添加更多的细节（回应意见）：我有一个人的名单。对于每个人，我都有一份他们最喜欢的其他人的列表，其中只包括主列表中的其他人。没有列表以任何方式排序。优先列表中的名称表示请求者希望与请求的人在一起。我正在寻找一种方法来创建指定数量的组，每个组只包含我在主列表中的人员。我希望分组能够包含首选项列表。如果他们都在他们的名单中要求彼此，它应该尝试将人们放在同一个小组中。它也应该包含一个人（在这个例子中是人A）请求其他人（人B）但B没有请求A的请求。在这种情况下，虽然它仍然应该计算请求，但它应该被计算为较低优先纳入而不是相互请求。

编辑：此外，按照要求，这里是一个JS函数，将（希望）有助于解释我的目标：

/* 
Scores a possible grouping 
group would be an object, where the keys are names and the values are arrays of preferences. Ex: 

    { 
     "Person 1": ["Person 2"], 
     "Person 2": ["Person 1"], 
     "Person 3": ["Person 4"], 
     "Person 4": ["Person 2"] 
    } 

*/ 
function getGroupScore(group) { 
    var totalPoints = 0; 

    //Add a point for each request 
    for (var person in group) { 
     for (var request in group[person]) { 
      if(request != undefined && request.length > 0) 
       totalPoints++; 
     } 
    } 

    //Add two points for each two-way request 
    for (var person in group) { 
     for (var request in group[person]) { 
      if (group[person][request] != undefined //String validation 
       && group[person][request].length > 0 //More string validation 
       && group[group[person][request]] != undefined //Array validation 
       && group[group[person][request]].indexOf(person) != -1) //Check mutual request 
        totalPoints += 2; 
     } 
    } 

    return totalPoints; 
} 

/* 
Compares two possble groupings 
*/ 
function compareGroups(groupA, groupB) { 
    var scoreA = getGroupScore(groupA), 
     scoreB = getGroupScore(groupB); 

    if (scoreA > scoreB) 
     return 1; 
    else if (scoreA == ScoreB) 
     return 0; 
    else 
     return -1; 
}

来源

2013-09-23 Wasabi Fan

你有*不知道*你会怎么做？是什么让你觉得我们会为你做你的功课？ –

可疑类似于http://stackoverflow.com/q/18965363/56778 –

不，这不是家庭作业，它是个人项目的一部分。我试图自己想出一个答案，但我的所有解决方案都会涉及到最初为每个组选择一个种子的人，而我发现这些人通常会将许多请求分开。我已经看到你在搜索后的日子里连接的问题，但它没有答案，所以它不能帮助我。 –

好，我一直在想你的问题，我想我可以给你一些方向，虽然我不能解决它。

首先我要试着重新修改一下你的问题，如果我错了，请纠正我的错误。

要有一个集合P人的，以及诸如偏好的一个表：

 
Preferences of 4 people named A B C D: 
    A B C D 
+---------+ 
A| X X | 
B|  X | 
C|  X X | 
D| X  | 
+---------+

在该示例中， 'A' 偏好 'C'， 'B' 喜欢 'd' 等对角线是否喜欢自己将变得无足轻重。

现在你的问题是将P人分成G个不同的大小为N的集合，假设P = G * N。对于N = 2的例子：

 
    A C B D 
+-------| 
A|x x| | 
C| x| x| 
+---+---- 
B| | x| 
D| |x | 
+---+---+ 
Here the partition is {A, C} and {B, D}

到其上的分区被满足的程度是X的对角块的数量，这在上面的例子中是3 + 2 = 5的总和。 AFAIK，与你想要解决的问题最相似的问题是构造一个块对角矩阵，或者尽可能地接近一个。在你的情况下，对角块外的值不会违反你。

如果你蛮横的问题，那么你有P！/ N！要检查的分区。对于较小的P值和较大的N值，这可能值得直接实施，尽管在JS中这样做会受到伤害。如果您的解决方案必须是最佳结果，那么您可能不得不采取这样的措施。

如果您可以允许“非常好”的解决方案，那么随机方法可能会接近。只要进行贪婪的重新排列，直到不再有重新排列，再重复这个过程几次。

我在其他论坛上也发现this thread可能对您有帮助。与此相关的大多数问题都假设存在一个满足每个偏好的解决方案，这归结为广度优先搜索。很明显，如果那是真的，那么结果将是您的最佳解决方案，但由于通常情况并非如此，您可能需要进行一些重大研究来修改已知算法。

最好的祝愿〜

来源

2013-09-26 03:12:08 DanielV

所以，你基本上建议我随机测试组，直到没有太大的改善？这绝对是我可以弄清楚如何实现的东西。 –

这是你想解决的问题吗？是的，如果“足够好”足够好，那么随机生成的多个贪婪测试可能是最简单的。 – DanielV

看完你的文章并思考了一段时间后，我想出了一个算法，似乎工作。感谢你的帮助！ –

根据偏好列表分配组（以3为例）

回答

相关问题