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

user_13378247 0
Viewed 61

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.

reverse-engineering sorting arrays javascript
3 Answers

You could count just the indices for a cetrtain name. As result, you get some groups which represents the preferences of the captain.

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

user_14476750

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)

user_20826730

Here is my own answer to my question. It works by giving each person a list of all their inferiors and superiors. An inferior would be someone who showed up above them in the list, but with a larger orig. The only way this can possibly happen is if the captain preferred them. And vice-versa for superiors.

Then any people that exist in both the inferiors and superiors list of someone are removed from those lists and put into an equals lists, meaning the captain has assigned them the exact same preference, because that's the only way they could have appeared to be simultaneously an inferior and superior.

Then people are ranked based on the length of their superiors list; people with no superiors are at the top. Those with the most superiors are at the bottom.

Then the equals groups are used to reconstruct the prefs object (all people who share the same equals groups are in the same group).

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

At the moment, this is the only answer which reliably solves the problem with only 100 lists of length 5. In fact it's fairly reliable with only half that many.

Also, this solution doesn't jumble up persons who have relationships with other persons; e.g. if Bob were to never appear with Ian, this would only prevent proper grouping, but not cause Bob and Ian to appear out of order with respect to each other.

The other answers do suffer from this defect.

user_133782470
Related