如何根据对象的排序方式推断对象的属性？

Question

如果你运行下面的代码片段，它会生成一个随机的人列表，每个人都有一个独特的orig属性，你可以假装这是他们到达机场的排队顺序（请多多包涵）。

船长不公平，不让人们按照他们到达的顺序坐在相应的座位上。他更喜欢一些名字而不是其他名字，并且同样喜欢一些名字。

他的偏好由prefs对象说明。 Bob, Sue, 和Sal是他最喜欢的名字，但他同样喜欢它们。 Ian并且Sam是他最不喜欢的，但他同样不喜欢他们。

所以这个不公平的船长根据他对他们名字的喜爱程度来招待他们。

这意味着人员列表首先按照他们到达的顺序排序，然后根据船长对他们名字的偏好再次排序。

当您运行代码片段时，它会生成一个对象列表，每个对象都只有一个name和orig（原始顺序）属性，并按上述方式排序。

假装船长的喜好是未知的。如果你生成一个足够长的列表，或者一个足够短的列表，你应该能够推断出这个prefs对象。

仅给出列表，如何推断prefs对象？

我需要一个基于许多短列表的解决方案，而不是基于一个非常长的列表的解决方案。

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

console.log(list);

这不是我的实际问题，但我希望这个简化版本很容易理解。如果我能解决这个问题，那么我就能解决我真正的问题。

Answer 1

这是我的尝试...在 generateList 之外我无权访问prefs对象或pref值，我只获得随机名称列表，然后尝试对列表进行逆向工程：let generateList = () => {&nbsp; const prefs = {&nbsp; &nbsp; Bob: { pref: 1 },&nbsp; &nbsp; Sue: { pref: 1 },&nbsp; &nbsp; Sal: { pref: 1 },&nbsp; &nbsp; Jim: { pref: 2 },&nbsp; &nbsp; Jon: { pref: 2 },&nbsp; &nbsp; Lyn: { pref: 2 },&nbsp; &nbsp; Ian: { pref: 3 },&nbsp; &nbsp; Sam: { pref: 3 }&nbsp; };&nbsp; const names = Object.keys(prefs);&nbsp; const randomName = () => names[~~(Math.random() * names.length)];&nbsp; const list = new Array(5).fill().map((_, orig) => {&nbsp; &nbsp; const name = randomName();&nbsp; &nbsp; return { name, orig };&nbsp; }).sort((a, b) => prefs[a.name].pref > prefs[b.name].pref ? 1 : -1);&nbsp; return list;}const lists = [];for (let i = 0; i < 10000; i++) {&nbsp; &nbsp; lists.push(generateList())}let guess = {};lists.forEach((list) => {&nbsp; &nbsp; list.forEach((item, index) => {&nbsp; &nbsp; &nbsp; &nbsp; guess[item.name] = (guess[item.name] || 0) + (list.length - index);&nbsp; &nbsp; });});// now we get the minimumconst min = Math.min(...Object.values(guess))const max = Math.max(...Object.values(guess))const offset = Math.round(max/min) + 1;// now we guess the key order (as best we can), and set the prefguess = Object.fromEntries(Object.entries(guess).map((item) => {&nbsp; &nbsp; item[1] = { pref: offset - Math.round(item[1]/min) };&nbsp; &nbsp; return item;}).sort((a,b) => a[1].pref - b[1].pref));console.log(guess)

Answer 2

您可以只计算某个名称的索引。结果，您得到一些代表船长偏好的组。function generateSet() {&nbsp; &nbsp; const&nbsp; &nbsp; &nbsp; &nbsp; 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 } },&nbsp; &nbsp; &nbsp; &nbsp; names = Object.keys(prefs),&nbsp; &nbsp; &nbsp; &nbsp; randomName = () => names[~~(Math.random() * names.length)];&nbsp; &nbsp; return Array&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .from({ length: 5 }, (_, orig) => ({ name: randomName(), orig }))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .sort((a, b) => prefs[a.name].pref - prefs[b.name].pref);}function count(n) {&nbsp; &nbsp; const result = {};&nbsp; &nbsp; for (let i = 0; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; generateSet().forEach(({ name }, i) => result[name] = (result[name] || 0) + i);&nbsp; &nbsp; }&nbsp; &nbsp; return result;}&nbsp;console.log(count(10000));

Answer 3

这是我自己对我的问题的回答。它的工作原理是为每个人提供一个包含所有inferiors和的列表superiors。Aninferior将是在列表中出现在他们之上的人，但具有更大的orig. 唯一可能发生这种情况的方法是船长更喜欢他们。反之亦然superiors。然后任何同时存在于someoneinferiors和superiorssomeone 列表中的人都会从这些列表中删除并放入equals列表中，这意味着船长已经为他们分配了完全相同的偏好，因为这是他们可能同时出现的唯一方式 an inferiorand superior。然后根据列表的长度对人们进行排名superiors；没有superiors的人在顶部。拥有最多superiors的人位于底部。然后这些equals组用于重建prefs对象（所有共享相同equals组的人都在同一组中）。const intersect = (a, b) => {&nbsp; return new Set([...a].filter(x => b.has(x)));}const setsEqual = (a, b) => [...a].sort().toString() == [...b].sort().toString();const prefs = {&nbsp; Bob: { pref: 1 },&nbsp; Sue: { pref: 1 },&nbsp; Sal: { pref: 1 },&nbsp; Jim: { pref: 2 },&nbsp; Jon: { pref: 2 },&nbsp; Lyn: { pref: 2 },&nbsp; Ian: { pref: 3 },&nbsp; Sam: { pref: 3 }};const names = Object.keys(prefs);const randomName = () => names[~~(Math.random() * names.length)];const randomList = () => new Array(5).fill().map((_, orig) => {&nbsp; const name = randomName();&nbsp; 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++) {&nbsp; const list = randomList();&nbsp; list.forEach(({ name }) => !people[name] && (people[name] = {&nbsp; &nbsp; superiors: new Set(), inferiors: new Set()&nbsp; }));&nbsp; list.forEach(({ name, orig }, yourPos) => {&nbsp; &nbsp; const superiors = people[name].superiors;&nbsp; &nbsp; const inferiors = people[name].inferiors;&nbsp; &nbsp; list.forEach((person, theirPos) => {&nbsp; &nbsp; &nbsp; if (person.name == name) return;&nbsp; &nbsp; &nbsp; if (theirPos < yourPos && person.orig > orig) {&nbsp; &nbsp; &nbsp; &nbsp; superiors.add(person.name);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; if (theirPos > yourPos && person.orig < orig) {&nbsp; &nbsp; &nbsp; &nbsp; inferiors.add(person.name);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; });&nbsp; });}Object.entries(people).forEach(([name, { superiors, inferiors }]) => {&nbsp; const intersection = intersect(superiors, inferiors);&nbsp; for (const elem of intersection) {&nbsp; &nbsp; superiors.delete(elem);&nbsp; &nbsp; inferiors.delete(elem);&nbsp; }});Object.entries(people).forEach(([yourName, person]) => {&nbsp; Object.entries(people).forEach(([theirName, other]) => {&nbsp; &nbsp; const yourInferiors = person.inferiors;&nbsp; &nbsp; const yourSuperiors = person.superiors;&nbsp; &nbsp; const theirInferiors = other.inferiors;&nbsp; &nbsp; const theirSuperiors = other.superiors;&nbsp; &nbsp; if (setsEqual(yourInferiors, theirInferiors) && setsEqual(yourSuperiors, theirSuperiors)) {&nbsp; &nbsp; &nbsp; person.equals = person.equals || new Set();&nbsp; &nbsp; &nbsp; other.equals = other.equals || new Set();&nbsp; &nbsp; &nbsp; person.equals.add(theirName);&nbsp; &nbsp; &nbsp; other.equals.add(yourName);&nbsp; &nbsp; &nbsp; person.equals.add(yourName);&nbsp; &nbsp; &nbsp; other.equals.add(theirName);&nbsp; &nbsp; }&nbsp; });});const rankedPeople = Object.entries(people).sort(([, a], [, b]) => {&nbsp; return a.superiors.size > b.superiors.size ? 1 : -1;}).map(([name, { equals }]) => {&nbsp; return { name, equals: [...equals].sort().toString() };});const groups = [...new Set(rankedPeople.map(({ equals }) => equals))]&nbsp; .map((group, pref) => ({ pref: pref + 1, group: group.split(',') }));const deduction = {};groups.forEach(({ pref, group }) => {&nbsp; group.forEach(name => {&nbsp; &nbsp; deduction[name] = pref;&nbsp; });});console.log(deduction);目前，这是唯一可靠地解决仅100包含 length 列表的问题的答案5。事实上，只有一半的数量是相当可靠的。此外，此解决方案不会混淆与其他人有关系的人；例如，如果 Bob 永远不会和 Ian 一起出现，这只会阻止正确的分组，但不会导致 Bob 和 Ian 彼此之间出现混乱。其他答案确实存在此缺陷。