How to generate all possible unique combinations of an array of objects, based on different properties

Question

I have an array of objects and want to create all possible unique combinations based on two keys.

Example input -

[
  { slot: 'body', spell: 'combat.i', item: 'body combat1'},
  { slot: 'body', spell: 'combat.i', item: 'body combat2'},
  { slot: 'body', spell: 'strength.i', item: 'body str1' },
  { slot: 'body', spell: 'dexterity.i', item: 'body dex1' },
  { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
  { slot: 'legs', spell: 'combat.i', item: 'legs combat1' },
  { slot: 'legs', spell: 'strength.i', item: 'legs str1' },
  { slot: 'head', spell: 'dexterity.i', item: 'head dex1' },
  { slot: 'head', spell: 'combat.i', item: 'head combat1' },
  { slot: 'head', spell: 'strength.i', item: 'head str1' },
]

The ideal output would be something like

[
  [
    { slot: 'body', spell: 'combat.i', item: 'body combat1' },
    { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
    { slot: 'head', spell: 'strength.i', item: 'head str1' },
  ],
  [
    { slot: 'body', spell: 'combat.i', item: 'body combat2' },
    { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
    { slot: 'head', spell: 'strength.i', item: 'head str1' },
  ],
  [
    { slot: 'body', spell: 'strength.i', item: 'body str' },
    { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
    { slot: 'head', spell: 'combat.i', item: 'head combat1' },
  ],
  ...etc
]

so that the final product would be all the combinations of each slot/spell/item without any repeats (disregarding the order).

My first thought was to organize the data into an a object for each slot and inside there an array for each effect.

const generateList = (data, slots, effects) => {
  const matches = {};
  slots.forEach(slot => {
    matches[slot] = {};
    effects.forEach(effect => {
      matches[slot][effect] = data.filter(item => item.slot === slot && item.spell === effect);
    })
  });

  return matches
};

Which generates

{
  body: {
    'combat.i': [
      { slot: 'body', spell: 'combat.i', item: 'body combat1' },
      { slot: 'body', spell: 'combat.i', item: 'body combat2' }
    ],
    'strength.i': [ { slot: 'body', spell: 'strength.i', item: 'body str1' } ],
    'dexterity.i': [ { slot: 'body', spell: 'dexterity.i', item: 'body dex1' } ]
  },
  legs: {
    'combat.i': [ { slot: 'legs', spell: 'combat.i', item: 'legs combat1' } ],
    'strength.i': [ { slot: 'legs', spell: 'strength.i', item: 'legs str1' } ],
    'dexterity.i': [ { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' } ]
  },
  head: {
    'combat.i': [ { slot: 'head', spell: 'combat.i', item: 'head combat1' } ],
    'strength.i': [ { slot: 'head', spell: 'strength.i', item: 'head str1' } ],
    'dexterity.i': [ { slot: 'head', spell: 'dexterity.i', item: 'head dex1' } ]
  },
]

I'm now kinda stuck on how to generate all the permutations to create the desired output, especially knowing that this will need to scale up to much larger numbers. I know the answer is something to do with recursion but for the life of me, my silly front-end brain can't figure it out. Any help would be appreciated!

Answer 1

Keep it short and simple:

function getTriples(items) {
  const result = [];
  for (const [i, firstItem] of items.entries()) {
    for (const [j, secondItem] of items.entries()) {
      for (const [k, thirdItem] of items.entries()) {
        if (i < j && j < k &&
            firstItem.slot != secondItem.slot && firstItem.slot != thirdItem.slot && secondItem.slot != thirdItem.slot &&
            firstItem.spell != secondItem.spell && firstItem.spell != thirdItem.spell && secondItem.spell != thirdItem.spell
        ) {
          result.push([firstItem, secondItem, thirdItem])
        }
      }
    }
  }
  return result;
}

document.body.textContent = JSON.stringify(getTriples([
  { slot: 'body', spell: 'combat.i', item: 'body combat1'},
  { slot: 'body', spell: 'combat.i', item: 'body combat2'},
  { slot: 'body', spell: 'strength.i', item: 'body str1' },
  { slot: 'body', spell: 'dexterity.i', item: 'body dex1' },
  { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
  { slot: 'legs', spell: 'combat.i', item: 'legs combat1' },
  { slot: 'legs', spell: 'strength.i', item: 'legs str1' },
  { slot: 'head', spell: 'dexterity.i', item: 'head dex1' },
  { slot: 'head', spell: 'combat.i', item: 'head combat1' },
  { slot: 'head', spell: 'strength.i', item: 'head str1' },
]), null, 4);
document.body.style = "white-space: pre; font-family: monospace";

Now to make this more generic for arbitrary combination sizes, you can use recursion instead of nesting the loops, but it gets a bit more complicated:

function getCombinations(size, items) {
  const result = [];
  function generate(combination, index) {
    if (combination.length >= size) {
      result.push(combination);
    } else {
      for (let i=index; i<items.length; i++) {
        const item = items[i];
        if (combination.every(prevItem =>
          prevItem.slot != item.slot && prevItem.spell != item.spell
        )) {
          generate([...combination, item], i+1);
        }
      }
    }
  }
  generate([], 0);
  return result;
}

Just ensure that the items contain more unique slot values and more unique spell values than the chosen size, or you'll get no results.

Finally, to make it generic over the properties that should be distinct between them items of one combination, you can introduce a parameter for those as well:

function getCombinations(properties, size, items) {
  const result = [];
  function generate(combination, index) {
    if (combination.length >= size) {
      result.push(combination);
    } else {
      for (let i=index; i<items.length; i++) {
        const item = items[i];
        if (properties.every(prop =>
          combination.every(prevItem =>
            prevItem[prop] != item[prop]
          )
        )) {
          generate([...combination, item], i+1);
        }
      }
    }
  }
  generate([], 0);
  return result;
}

document.body.textContent = JSON.stringify(getCombinations(['slot', 'spell'], 3, [
  { slot: 'body', spell: 'combat.i', item: 'body combat1'},
  { slot: 'body', spell: 'combat.i', item: 'body combat2'},
  { slot: 'body', spell: 'strength.i', item: 'body str1' },
  { slot: 'body', spell: 'dexterity.i', item: 'body dex1' },
  { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
  { slot: 'legs', spell: 'combat.i', item: 'legs combat1' },
  { slot: 'legs', spell: 'strength.i', item: 'legs str1' },
  { slot: 'head', spell: 'dexterity.i', item: 'head dex1' },
  { slot: 'head', spell: 'combat.i', item: 'head combat1' },
  { slot: 'head', spell: 'strength.i', item: 'head str1' },
]), null, 4);
document.body.style = "white-space: pre; font-family: monospace";