これは、純粋にアルゴリズムの観点から始まった質問の 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;
}