Find and group common elements across objects in an array

Question

I am trying to figure out how to map a new array of objects that kind of creates teams by checking each array of users and, where there is a common users, moving that entire array into a new property that also features the notebookIds in common.

I have an array of objects structured like so:

const usersByNotebooks = 
[
{
    "notebookId": "abc",
    "users": [1, 2, 3, 4]
  },
  {
    "notebookId": "cde",
    "users": [2, 3, 4]
  },
  {
    "notebookId": "fgh",
    "users": [3, 4, 5]
  },
  {
    "notebookId": "qqq",
    "users": [33, 16, 12]
  },
]

So for the above data it would become something like this:

const teams = 
[
{
    "notebooksOnTeam": ["abc", "cde", "fgh"],
    "usersOnTeam": [1, 2, 3, 4, 5]
  },
  {
    "notebooksOnTeam": "qqq",
    "usersOnTeam": [33, 16, 12]
  },
]

I am using javascript and having trouble getting the logic down.

You are attempting to find "connected components". You have bipartite graph: nodes in the "notebooks" set are connected to nodes in the "users" set. You want to find disjoint subsets of that graph. Your question is related to [Finding All Connected Components of an Undirected Graph](https://stackoverflow.com/questions/21900713/finding-all-connected-components-of-an-undirected-graph) — Wyck, Feb 19 '23 at 17:23

score 0 · Answer 1 · answered Feb 19 '23 at 08:18

Loop over objects of array using reduce and check:
If the current notebook's users don't match any existing team with find method, so create a new team.
If the current notebook's users match an existing team, add the notebook to that team.

const usersByNotebooks = [{ "notebookId": "abc", "users": [1, 2, 3, 4] }, { "notebookId": "cde", "users": [2, 3, 4] }, { "notebookId": "fgh", "users": [3, 4, 5] }, { "notebookId": "qqq", "users": [33, 16, 12] }, ]; 
const teams = usersByNotebooks.reduce((result, current) => {
  const teamFound = result.find((team) => team.usersOnTeam.some((user) => current.users.includes(user)));

  if (!teamFound) {
    result.push({
      notebooksOnTeam: [current.notebookId],
      usersOnTeam: current.users
    });
  } else {
    teamFound.notebooksOnTeam.push(current.notebookId);
    current.users.forEach((user) => {
      if (!teamFound.usersOnTeam.includes(user)) {
        teamFound.usersOnTeam.push(user);
      }
    });
  }
  return result;
}, []);
console.log(teams)

Nina Scholz · Answer 2 · 2023-02-21T09:52:14.457

You could have a look to any objects of the result set and either get the first object of the same group and add all other found and finally add the actual value or later add a new object.

This approach works for unsorted and not connected items which gets later a joint.

const
    addIfNotExist = (array, value) => array.includes(value) || array.push(value),
    usersByNotebooks = [{ notebookId: "abc", users: [1, 2, 3, 4] }, { notebookId: "cde", users: [2, 3, 4] }, { notebookId: "fgh", users: [3, 4, 5] }, { notebookId: "qqq", users: [33, 16, 12] }, { notebookId: "xxx", users: [6, 7] }, { notebookId: "yyy", users: [5, 6] }],
    result = usersByNotebooks.reduce(
        (r, { notebookId, users }) => users.reduce((s, user) => {
            const objects = [];
            let first;
            for (const o of s) {
                if (!o.users.includes(user) && !o.notebooks.includes(notebookId)) {
                    objects.push(o);
                    continue;
                }
                if (!first) objects.push(first = o);

                o.users.forEach(addIfNotExist.bind(null, first.users));
                o.notebooks.forEach(addIfNotExist.bind(null, first.notebooks));
            }

            if (first) {
                addIfNotExist(first.users, user);
                addIfNotExist(first.notebooks, notebookId);
            } else {
                objects.push({ users: [user], notebooks: [notebookId] });
            }
            return objects;
        }, r),
        []
    );

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

This is an abstract solution for any length of groups (at least two) which are connected.

It works in three step:

Generate an array of pairs or more or less items in a tupel,
group connected items together in an aray of arrays and
map the items in the wanted format.

const
    addIfNotExist = (array, value) => array.includes(value) || array.push(value),
    groupConnectedParts = (r, a) => {
        const objects = [];
        let first;
        for (const b of r) {
            if (!a.some((v, i) => b[i].includes(v))) {
                objects.push(b);
                continue;
            }
            if (!first) objects.push(first = b);
            b.forEach((group, i) => group.forEach(addIfNotExist.bind(null, first[i])));
        }

        if (first) a.forEach((v, i) => addIfNotExist(first[i], v));
        else objects.push(a.map(v => [v]));

        return objects;
    },
    usersByNotebooks = [{ notebookId: "abc", users: [1, 2, 3, 4] }, { notebookId: "cde", users: [2, 3, 4] }, { notebookId: "fgh", users: [3, 4, 5] }, { notebookId: "qqq", users: [33, 16, 12] }, { notebookId: "xxx", users: [6, 7] }, { notebookId: "yyy", users: [5, 6] }],
    result = usersByNotebooks
        .flatMap(({ notebookId, users }) => users.map(user => [notebookId, user]))
        .reduce(groupConnectedParts, [])
        .map(([notebooks, users]) => ({ notebooks, users }));

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Find and group common elements across objects in an array

2 Answers2