Home > Net >  Compare 2 arrays by multi-criteria
Compare 2 arrays by multi-criteria

Time:10-12

I have 2 lists, one is a list of people with associated activities, and the other is a list of required activities. I am trying to match the activities from the two lists and extract the list of people that match all activities. I started with the array filter prototype but could only get it working for one requirement, and even then it was not tied to the query array. The list of requirements is dynamically generated and could be 1 to 10 depending on the position.

An added wrinkle that I'm not trying to address here is that the requirements could be required or preferred. I'll jump off that bridge when I get there. For this question, the weight property can be ignored.

var users = [{candidate: '10',activity: '37'},
             {candidate: '10',activity: '43'},
             {candidate: '1',activity: '181'},
             {candidate: '10',activity: '181'},
             {candidate: '2',activity: '43'},
             {candidate: '2',activity: '181'},
             {candidate: '5',activity: '43'},
             {candidate: '1',activity: '37'},
             {candidate: '5',activity: '27'},
             {candidate: '1',activity: '173'}];

var query = [{activity: '181', weight: 'Required'},
             {activity: '43', weight: 'Required'},
             {activity: '37', weight: 'Preferred'}];

const items = users.filter(item => item.activity.indexOf('37') !== -1);

console.log(items);

CodePudding user response:

You could assign to each activity a value, like 1, 2, 4, etc and sum the needed values and filter later the candidates who have the wanted activities.

const
    users = [{ candidate: '10', activity: '37' }, { candidate: '10', activity: '43' }, { candidate: '1', activity: '181' }, { candidate: '10', activity: '181' }, { candidate: '2', activity: '43' }, { candidate: '2', activity: '181' }, { candidate: '5', activity: '43' }, { candidate: '1', activity: '37' }, { candidate: '5', activity: '27' }, { candidate: '1', activity: '173' }],
    query = [{ activity: '181', weight: 'Required' }, { activity: '43', weight: 'Required' }, { activity: '37', weight: 'Preferred' }],
    values = Object.fromEntries(query.map(({ activity }, i) => [activity, 1 << i])),
    activities = users.reduce((r, { candidate, activity }) => {
        r[candidate] = (r[candidate] || 0)   (values[activity] || 0);
        return r;
    }, {}),
    candidates = Object
        .keys(activities)
        .filter(k => activities[k] === (1 << query.length) - 1);
    
console.log(candidates);
console.log(activities );
.as-console-wrapper { max-height: 100% !important; top: 0; }

Another approach checks the weights and returns an array of users which matches at least some of the weights.

It is still unclear, which one of the weights should have priority. This would shape the result set.

const
    users = [{ candidate: '10', activity: '37' }, { candidate: '10', activity: '43' }, { candidate: '1', activity: '181' }, { candidate: '10', activity: '181' }, { candidate: '2', activity: '43' }, { candidate: '2', activity: '181' }, { candidate: '5', activity: '43' }, { candidate: '1', activity: '37' }, { candidate: '5', activity: '27' }, { candidate: '1', activity: '173' }],
    query = [{ activity: '181', weight: 'Required' }, { activity: '43', weight: 'Required' }, { activity: '37', weight: 'Preferred' }],
    { counts, values } = query.reduce((r, { activity, weight }, i) => {
        r.values[activity] = weight;
        r.counts[weight] = (r.counts[weight] || 0)   1;
        return r;
    }, { counts: {}, values: {} }),
    activities = users.reduce((r, { candidate, activity }) => {
        if (!values[activity]) return r;
        const weight = values[activity];
        r[candidate] ??= {};
        r[candidate][weight] = (r[candidate][weight] || 0)   1;
        return r;
    }, {}),
    candidates = Object
        .entries(activities)
        .reduce((r, [candidate, o]) => {
            const weights = Object.keys(counts).filter(weight => o[weight] === counts[weight]);
            if (weights.length) r.push({ candidate, weights });
            return r;
        }, []);
  
console.log(candidates);
console.log(activities);
console.log(values);
console.log(counts);
.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response:

We can group users by the candidate value...

// returns { candidate: [ users ], candidate: [ users ], ...
const grouped = users.reduce((acc, user) => {
  if (!acc[user.candidate]) acc[user.candidate] = [];
  acc[user.candidate].push(user);
  return acc;
}, {});

Now we can ask for the activities of a given user...

// returns [ activities ]
function activities(user) {
  return grouped[user.candidate].map(u => u.activity);
}

We can ask if all of the required activity ids are present in an array of activity ids.

// returns a bool, true if every required activity is in activities param
function sufficient(activities) {
  // required activities defined by the op
  return required.every(a => activities.includes(a.activity));
}

With these tools, we can make a list of candidates who have all required activities...

// returns { candidate: bool, ... }
users.reduce((acc, user) => {
  acc[user.candidate] = sufficient(activities(user));
  return acc;
}, {});

Demo ...

const users = [
  {candidate: '10',activity: '37'},
  {candidate: '10',activity: '43'},
  {candidate: '1',activity: '181'},
  {candidate: '10',activity: '181'},
  {candidate: '2',activity: '43'},
  {candidate: '2',activity: '181'},
  {candidate: '5',activity: '43'},
  {candidate: '1',activity: '37'},
  {candidate: '5',activity: '27'},
  {candidate: '1',activity: '173'}
];

const required = [
  {activity: '181', weight: 'Required'},
  {activity: '43', weight: 'Required'},
  {activity: '37', weight: 'Preferred'}
];

const grouped = users.reduce((acc, user) => {
  if (!acc[user.candidate]) acc[user.candidate] = [];
  acc[user.candidate].push(user);
  return acc;
}, {});

function activities(user) {
  return grouped[user.candidate].map(u => u.activity);
}

function sufficient(activities) {
  return required.every(a => activities.includes(a.activity));
}

const results = users.reduce((acc, user) => {
  acc[user.candidate] = sufficient(activities(user));
  return acc;
}, {});

console.log(results);

CodePudding user response:

If I got it correctly and the intention is to create a list of candidates based on their activity and ranked by Required then Preferred weight, then it may be done like this:

var users = [{candidate: '10',activity: '37'},
             {candidate: '10',activity: '43'},
             {candidate: '1',activity: '181'},
             {candidate: '10',activity: '181'},
             {candidate: '2',activity: '43'},
             {candidate: '2',activity: '181'},
             {candidate: '5',activity: '43'},
             {candidate: '1',activity: '37'},
             {candidate: '5',activity: '27'},
             {candidate: '1',activity: '173'}];

var query = [{activity: '181', weight: 'Required'},
             {activity: '43', weight: 'Required'},
             {activity: '37', weight: 'Preferred'}];

let candidates = new Map;

const items = users.forEach(function ({candidate, activity}) {
  const a = this.get(activity);
  if (!a)
    return;
  const c = candidates.get(candidate) ?? {candidate};
  c.Required = (c.Required ?? 0)   (a.weight === 'Required');
  c.Preferred = (c.Preferred ?? 0)   (a.weight === 'Preferred');
  candidates.set(candidate, c);
}, new Map(query.map(q => [q.activity, q])));

candidates = [...candidates].sort((a, b) => {
  const [, {Required: ar, Preferred: ap}] = a, [, {Required: br, Preferred: bp}] = b;
  return br - ar || bp - ap;
}).map(([, value]) => value);

console.log(candidates);

CodePudding user response:

You can start by grouping all activities per user and then use Array#every to dynamically test every required activity with either Array#reduce or Array#map, if you need a boolean result for each user, or Array#filter, if you need just the user(s) meeting the requirements:

const users = [{candidate: '10',activity: '37'}, {candidate: '10',activity: '43'}, {candidate: '1',activity: '181'}, {candidate: '10',activity: '181'}, {candidate: '2',activity: '43'}, {candidate: '2',activity: '181'}, {candidate: '5',activity: '43'}, {candidate: '1',activity: '37'}, {candidate: '5',activity: '27'}, {candidate: '1',activity: '173'}],

query = [{activity: '181', weight: 'Required'}, {activity: '43', weight: 'Required'}, {activity: '37', weight: 'Preferred'}],
             
grouped = users.reduce(
    (group, {candidate:cand,activity:act}) =>
    ({...group, [cand]:[...(group[cand] || []),act]}), {}
);

items = Object.entries(grouped).filter(
    ([candidate,activities]) => 
    query.every(({activity}) => activities.includes(activity))
);

console.log(items);

CodePudding user response:

In the general case, there are two stages: converting the data to a form that's easily filtered based upon the criteria, and then filtering the data.

Sets are generally the choice to compare collections of values. Unfortunately, the Set class in JavaScript has limited support for standard set operations, though they can be easily implemented (as the MDN page shows).

With a suitable implementation for the subset relation, the first stage for the desired query system could be implemented by converting users to a map (as either a Map or plain object) from user IDs to their activities, and the criteria to sets containing the required and preferred activities.

For the second stage, JavaScript is (also) missing a filter function for objects & Maps, though each can be converted to a suitable array which can then be filtered. The filtered entries can then be converted back to a map, if desirable.

// from MDN
function isSuperset(set, subset) {
    for (const elem of subset) {
        if (! set.has(elem)) {
            return false;
        }
    }
    return true;
}

// data
var users = [
    {candidate: '10',activity: '37'},
    {candidate: '10',activity: '43'},
    {candidate: '1',activity: '181'},
    {candidate: '10',activity: '181'},
    {candidate: '2',activity: '43'},
    {candidate: '2',activity: '181'},
    {candidate: '5',activity: '43'},
    {candidate: '1',activity: '37'},
    {candidate: '5',activity: '27'},
    {candidate: '1',activity: '173'},
];

var criteria = [
    {activity: '181', weight: 'Required'},
    {activity: '43', weight: 'Required'},
    {activity: '37', weight: 'Preferred'},
];

// stage 1: convert users to map<int, set>
let userActivities = users.reduce((acts, {candidate, activity}) => {
    acts[candidate] ??= new Set();
    acts[candidate].add(activity);
    return acts;
}, {});
// using Map
/*
let userActivities = users.reduce((acts, {candidate, activity}) => {
    acts.has(candidate) || (acts.set(candidate, new Set()));
    acts.get(candidate).add(activity);
    return acts;
}, new Map());
*/

// convert criteria to a set
let query = criteria.reduce((acts, {activity, weight}) => {
    acts.add(activity);
    return acts;
}, new Set());

// stage 2:
let items = Object.entries(userActivities).filter(
    ([id, acts]) => isSuperset(acts, query)
);
// using Map
//let items = [...userActivities.entries()].filter(...);

// results
// console.log on SO doesn't like to show Set elements, so convert them to arrays for display purposes
console.log(Object.fromEntries(items.map(([id, acts]) => [id, [...acts]])));
// using Map, filtered entries can be converted back with:
//new Map(items);

More complex queries should be expressible as set operations without much difficulty.

  • Related