Get array of combinations based on array of objects

Question

I have the following array:

const arr = [
  {
    _id: '60c936bca0bd431287ae698b',
    name: 'Markets',
    referential: '60c936bca0bd431287ae6988'
  },
  {
    _id: '60c93b17a0bd431287ae69a0',
    name: 'eRetailers',
    referential: '60c93b17a0bd431287ae699f'
  },
  {
    _id: '60d0a30d303ebd2a19d6fb4d',
    name: 'Products',
    referential: '60d0a30d303ebd2a19d6fb4b'
  },
  {
    _id: '60c936bca0bd431287ae6989',
    name: 'Regions',
    referential: '60c936bca0bd431287ae6988'
  },
  {
    _id: '60d0a30d303ebd2a19d6fb4c',
    name: 'Segments',
    referential: '60d0a30d303ebd2a19d6fb4b'
  }
];

Now I want an array of all the possible combination of the array above, with one condition: a combination cannot contain two objects have the same referential.

Here is the full list of the desired combinations:

Aggregations level 1 :
Products
Segments
Markets
Regions
eRetailers

Aggregations level 2 :
Products/Markets
Products/Regions
Products/eRetailers
Segments/Markets
Segments/Regions
Segments/eRetailers
Markets/Products
Markets/Segments
Markets/eRetailers
Regions/eRetailers
Regions/Products
Regions/Segments
eRetailers/Markets
eRetailers/Regions
eRetailers/Products
eRetailers/Segments

Aggregations Niveau 3 :
Products/Regions/eRetailers
Products/eRetailers/Regions
Segments/Markets/eRetailers
Segments/eRetailers/Markets
Segments/Regions/eRetailers
Segments/eRetailers/Regions
Markets/eRetailers/Segments
Markets/Segments/eRetailers
Regions/Products/eRetailers
Regions/eRetailers/products
Regions/Segments/eRetailers
Regions/eRetailers/PSegments
eRetailers/Regions/Products
eRetailers/Products/Regions
eRetailers/Markets/Segments
eRetailers/Segments/Markets
eRetailers/Regions/Segments
eRetailers/Segments/Regions

Here's the current code which is not working properly:

function combinator (s) {
   list_of_strings = new Array();
   for(i=0;i<s.length;i++) {
       for(j=i+1;j<s.length+1;j++) {
           list_of_strings.push(s.slice(i, j));
       }
   }
   return list_of_strings;
}

console.log(combinator(arr));

I guess you could use FlatMap for this. Something like const result = arr.flatMap( (curVal, idx, myArr) => arr.slice(idx + 1).map(item => ``${curVal.name}/${item.name} ) );` — tpliakas
– tpliakas, Commented Jun 21, 2021 at 23:20
First thing that comes to my mind, is that nowhere in your code any referentials are compared — TostMaster
– TostMaster, Commented Jun 22, 2021 at 8:45

tao · Accepted Answer · 2021-06-22 09:00:23Z

Here's my approach:

I've made a recursive parsing function (parseLevel) which, if the depth level has not been reached, is looking for any other item having a ref different than the ones already used. In order to achieve this, I pass it the following params:

refs - already used refs (filtering),
ids,
acc - accumulator,
depth - current depth level
level - required number of items in a permutation

const arr = [{
    _id: '60c936bca0bd431287ae698b',
    name: 'Markets',
    referential: '60c936bca0bd431287ae6988'
  },
  {
    _id: '60c93b17a0bd431287ae69a0',
    name: 'eRetailers',
    referential: '60c93b17a0bd431287ae699f'
  },
  {
    _id: '60d0a30d303ebd2a19d6fb4d',
    name: 'Products',
    referential: '60d0a30d303ebd2a19d6fb4b'
  },
  {
    _id: '60c936bca0bd431287ae6989',
    name: 'Regions',
    referential: '60c936bca0bd431287ae6988'
  },
  {
    _id: '60d0a30d303ebd2a19d6fb4c',
    name: 'Segments',
    referential: '60d0a30d303ebd2a19d6fb4b'
  }
];
const refIds = [...new Set(arr.map(({referential}) => referential))].map(ref => ({
  ref,
  _ids: arr.filter(({referential}) => referential === ref).map(({_id}) => _id)
}));

function getPermutations(level) {
  return refIds.reduce((acc, {ref, _ids}) => {
    _ids
      .forEach(id => parseLevel({
        depth: 1,
        level,
        refs: [ref],
        ids: [id],
        acc
      }));
    return acc;
  }, [])
}

function parseLevel({depth, level, refs, ids, acc}) {
  if (depth === level) {
    acc.push(ids.map(id => getItemName(id)).join('/'))
  } else {
    refIds
      .filter(({ref}) => !refs.includes(ref))
      .forEach(({ref, _ids}) => _ids
        .forEach(id => parseLevel({
          depth: depth + 1,
          level,
          refs: [...refs, ref],
          ids: [...ids, id],
          acc
        }))
      );
  }
}

function getItemName(id) {
  return arr.find(({_id}) => _id === id).name
}

console.log(Object.assign({}, 
  ...[1, 2, 3, 4].map(i => ({ [i + ' permutations']: getPermutations(i) })),
  { refIds }
))

Because the requirement is to create combinations of items with unique refs, I start by creating an array of all distinct refs: refIds. In each of them I'm also placing ids of all elements having that ref. This step is not really necessary, but it ensures we don't iterate through items which would be excluded anyways (because they have the same ref).

I then start creating results by going through each id of each refId element, placing its id into ids (and its ref into refs) and then run parseLevel, which looks for any element having a ref not yet present in refs. If it finds one, it does the same: ads its id to ids and its ref into refs. Then it runs parseLevel again.
Each time it runs, it first checks if the desired depth level has been reached. If so, it transforms the ids into names, because that's what we want to present.

The obvious advantage is recursivity here: it means this will work with any number of different refs (therefore any number of levels). The only condition I took for granted is that each element has a unique _id.

Collectives™ on Stack Overflow

Get array of combinations based on array of objects

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related