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

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 = () => {

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

  return list;

}

const lists = [];

for (let i = 0; i < 10000; i++) {

    lists.push(generateList())

}

let guess = {};

lists.forEach((list) => {

    list.forEach((item, index) => {

        guess[item.name] = (guess[item.name] || 0) + (list.length - index);

    });

});

// now we get the minimum

const 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 pref

guess = Object.fromEntries(Object.entries(guess).map((item) => {

    item[1] = { pref: offset - Math.round(item[1]/min) };

    return item;

}).sort((a,b) => a[1].pref - b[1].pref));

console.log(guess)

Answer 2

您可以只计算某个名称的索引。结果，您得到一些代表船长偏好的组。

function generateSet() {

    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 } },

        names = Object.keys(prefs),

        randomName = () => names[~~(Math.random() * names.length)];

    return Array

            .from({ length: 5 }, (_, orig) => ({ name: randomName(), orig }))

            .sort((a, b) => prefs[a.name].pref - prefs[b.name].pref);

}

function count(n) {

    const result = {};

    for (let i = 0; i < n; i++) {

        generateSet().forEach(({ name }, i) => result[name] = (result[name] || 0) + i);

    }

    return result;

} 

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) => {

  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 彼此之间出现混乱。

其他答案确实存在此缺陷。