如何根据对象的排序方式推断对象的属性？
How to infer the properties of objects based on how they were sorted?
如果您 运行 下面的代码片段，它会生成一个随机人员列表，每个人都有一个独特的 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);
这不是我的实际问题，但我希望这个简化版很容易理解。如果我能解决这个问题，那么我就能解决我真正的问题。
您可以只计算某个名称的索引。结果，你得到一些代表船长喜好的组。
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));
这是我的尝试...在 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)
这是我自己对我的问题的回答。它的工作原理是为每个人提供一份包含所有 inferiors 和 superiors 的列表。 inferior 将是在列表中出现在他们之上的人，但 orig 更大。唯一可能发生这种情况的方法是船长更喜欢他们。 superiors.
反之亦然
然后任何同时存在于某人的 inferiors 和 superiors 列表中的人都会从这些列表中删除并放入 equals 列表中，这意味着船长已经为他们分配了完全相同的偏好，因为这是他们看起来同时是 inferior 和 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 个长度为 5 的问题的答案。事实上，它是相当可靠的，只有一半。
此外，此解决方案不会混淆与其他人有关系的人；例如如果 Bob 永远不会和 Ian 一起出现，这只会阻止正确的分组，但不会导致 Bob 和 Ian 彼此之间出现混乱。
其他答案确实存在此缺陷。
如果您 运行 下面的代码片段，它会生成一个随机人员列表，每个人都有一个独特的 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);
这不是我的实际问题，但我希望这个简化版很容易理解。如果我能解决这个问题，那么我就能解决我真正的问题。
您可以只计算某个名称的索引。结果，你得到一些代表船长喜好的组。
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));
这是我的尝试...在 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)
这是我自己对我的问题的回答。它的工作原理是为每个人提供一份包含所有 inferiors 和 superiors 的列表。 inferior 将是在列表中出现在他们之上的人，但 orig 更大。唯一可能发生这种情况的方法是船长更喜欢他们。 superiors.
然后任何同时存在于某人的 inferiors 和 superiors 列表中的人都会从这些列表中删除并放入 equals 列表中，这意味着船长已经为他们分配了完全相同的偏好，因为这是他们看起来同时是 inferior 和 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 个长度为 5 的问题的答案。事实上，它是相当可靠的，只有一半。
此外，此解决方案不会混淆与其他人有关系的人；例如如果 Bob 永远不会和 Ian 一起出现，这只会阻止正确的分组，但不会导致 Bob 和 Ian 彼此之间出现混乱。
其他答案确实存在此缺陷。