這是我自己對我的問題的回答。它的工作原理是為每個人提供一個包含所有inferiors和的列表superiors。Aninferior將是在列表中出現在他們之上的人，但具有更大的orig. 唯一可能發生這種情況的方法是船長更喜歡他們。反之亦然superiors。
然后任何同時存在于someoneinferiors和superiorssomeone 列表中的人都會從這些列表中刪除并放入equals列表中，這意味著船長已經為他們分配了完全相同的偏好，因為這是他們可能同時出現的唯一方式 an inferiorand superior。
然后根據列表的長度對人們進行排名superiors；沒有superiors的人在頂部。擁有最多superiors的人位于底部。
然后這些equals組用于重建prefs對象（所有共享相同equals組的人都在同一組中）。
const intersect = (a, b) => {
return new Set([...a].filter(x => b.has(x)));
}
const setsEqual = (a, b) => [...a].sort().toString() == [...b].sort().toString();
const prefs = {
Bob: { pref: 1 },
Sue: { pref: 1 },
Sal: { pref: 1 },
Jim: { pref: 2 },
Jon: { pref: 2 },
Lyn: { pref: 2 },
Ian: { pref: 3 },
Sam: { pref: 3 }
};
const names = Object.keys(prefs);
const randomName = () => names[~~(Math.random() * names.length)];
const randomList = () => new Array(5).fill().map((_, orig) => {
const name = randomName();
return { name, orig };
}).sort((a, b) => prefs[a.name].pref > prefs[b.name].pref ? 1 : -1);
const people = {};
for (let i = 0; i < 100; i++) {
const list = randomList();
list.forEach(({ name }) => !people[name] && (people[name] = {
superiors: new Set(), inferiors: new Set()
}));
list.forEach(({ name, orig }, yourPos) => {
const superiors = people[name].superiors;
const inferiors = people[name].inferiors;
list.forEach((person, theirPos) => {
if (person.name == name) return;
if (theirPos < yourPos && person.orig > orig) {
superiors.add(person.name);
}
if (theirPos > yourPos && person.orig < orig) {
inferiors.add(person.name);
}
});
});
}
Object.entries(people).forEach(([name, { superiors, inferiors }]) => {
const intersection = intersect(superiors, inferiors);
for (const elem of intersection) {
superiors.delete(elem);
inferiors.delete(elem);
}
});
Object.entries(people).forEach(([yourName, person]) => {
Object.entries(people).forEach(([theirName, other]) => {
const yourInferiors = person.inferiors;
const yourSuperiors = person.superiors;
const theirInferiors = other.inferiors;
const theirSuperiors = other.superiors;
if (setsEqual(yourInferiors, theirInferiors) && setsEqual(yourSuperiors, theirSuperiors)) {
person.equals = person.equals || new Set();
other.equals = other.equals || new Set();
person.equals.add(theirName);
other.equals.add(yourName);
person.equals.add(yourName);
other.equals.add(theirName);
}
});
});
const rankedPeople = Object.entries(people).sort(([, a], [, b]) => {
return a.superiors.size > b.superiors.size ? 1 : -1;
}).map(([name, { equals }]) => {
return { name, equals: [...equals].sort().toString() };
});
const groups = [...new Set(rankedPeople.map(({ equals }) => equals))]
.map((group, pref) => ({ pref: pref + 1, group: group.split(',') }));
const deduction = {};
groups.forEach(({ pref, group }) => {
group.forEach(name => {
deduction[name] = pref;
});
});
console.log(deduction);
目前，這是唯一可靠地解決僅100包含 length 列表的問題的答案5。事實上，只有一半的數量是相當可靠的。
此外，此解決方案不會混淆與其他人有關系的人；例如，如果 Bob 永遠不會和 Ian 一起出現，這只會阻止正確的分組，但不會導致 Bob 和 Ian 彼此之間出現混亂。
其他答案確實存在此缺陷。
