How to infer the properties of objects based on how they were sorted?

Question

If you run the code snippet below, it will generate a list of random people, each with a unique orig attribute, which you can pretend is the order they arrived in line at the airport (please bear with me).

The captain isn't fair and doesn't let people sit in seats corresponding to the order they arrived. He prefers some names over others, and some names equally.

His preferences are illustrated by the prefs object. Bob, Sue, and Sal are his favorite names, but he likes them equally. Ian and Sam are his least favorite, but he dislikes them both equally.

So this unfair captain resorts the people based on how much he likes their name.

This means the list of people is sorted first by the order they arrived, and then sorted again by the captain's preference for their names.

When you run the code snippet, it generates a list of objects each with only a name and orig (original order) property, sorted as described above.

Pretend the captain's preferences are unknown. If you generate a long enough list, or a short one enough times, you should be able to deduce the prefs object.

How does one deduce the prefs object, given only lists?

I need a solution based on many short lists, as opposed to a solution based on a single very long list.

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

This is not my actual problem, but I hope this reduced version is easy to understand. If I can solve this then I can solve my real problem.

Answer 1

Here's my attempt... outside generateList I have no access to the prefs object or to the pref value, I only get the list of random names, and then attempt to reverse engineer the list:

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)