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

Answer 2

You need to organize the data by 'slot' first, and then by 'spell' within each slot is a good start. After organizing the data, you can generate the combinations.

# Example input
items = [
    {'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'},
]

# Step 1: Organize the data
organized = {}
for item in items:
    slot = item['slot']
    spell = item['spell']
    if slot not in organized:
        organized[slot] = {}
    if spell not in organized[slot]:
        organized[slot][spell] = []
    organized[slot][spell].append(item)

# Step 2: Generate combinations
# Convert each slot's spells into a list of items
slot_combinations = [list(spell.values()) for spell in organized.values()]
# Generate all combinations using product
all_combinations = list(product(*[item for sublist in slot_combinations for item in sublist]))

# Convert from tuple back to list format for the final output
final_combinations = [[item for item in combo] for combo in all_combinations]

# Example to print the first 5 combinations for brevity
for combo in final_combinations[:5]:
    print(combo)

Answer 3

const items = [
    { slot: 'body', spell: 'combat.i', item: 'body combat1' },
    { slot: 'body', spell: 'combat.i', item: 'body combat2' },
    // Other items...
];

// Organize the data
let organized = {};
items.forEach(item => {
    if (!organized[item.slot]) {
        organized[item.slot] = {};
    }
    if (!organized[item.slot][item.spell]) {
        organized[item.slot][item.spell] = [];
    }
    organized[item.slot][item.spell].push(item);
});

// Generate combinations
function cartesian(...args) {
    var r = [], max = args.length-1;
    function helper(arr, i) {
        for (var j=0, l=args[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(args[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

let slotCombinations = Object.values(organized).map(spell => Object.values(spell).flat());
let allCombinations = cartesian(...slotCombinations);

// Example to print the first 5 combinations for brevity
allCombinations.slice(0, 5).forEach(combo => console.log(combo));

Answer 4

I'm not sure if this is what you want :

function generateAllUniqueCombinations(items) {
  // Group items by their slot and then by spell within each slot to facilitate combination generation.
  const groupedBySlotAndSpell = items.reduce((acc, item) => {
    if (!acc[item.slot]) acc[item.slot] = {};
    if (!acc[item.slot][item.spell]) acc[item.slot][item.spell] = [];
    acc[item.slot][item.spell].push(item);
    return acc;
  }, {});

  // Generate all combinations of spells for each slot.
  function findAllSpellCombinations(slots) {
    if (slots.length === 0) return [[]];

    const firstSlotSpells = Object.keys(groupedBySlotAndSpell[slots[0]]);
    const combinationsWithoutFirst = findAllSpellCombinations(slots.slice(1));

    let allCombinations = [];
    firstSlotSpells.forEach((spell) => {
      combinationsWithoutFirst.forEach((combination) => {
        allCombinations.push([{ slot: slots[0], spell }, ...combination]);
      });
    });

    return allCombinations;
  }

  // Convert the slot-spell combinations into item combinations.
  function toItemCombinations(spellCombinations) {
    return spellCombinations.map((combination) =>
      combination.map(
        ({ slot, spell }) =>
          groupedBySlotAndSpell[slot][spell].find((item) => true) // Simply select the first matching item
      )
    );
  }

  const slots = Object.keys(groupedBySlotAndSpell);
  const spellCombinations = findAllSpellCombinations(slots);

  return toItemCombinations(spellCombinations);
}

// Example usage with the provided input array
const items = [
  { 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" },
];

const uniqueCombinations = generateAllUniqueCombinations(items);
console.log(uniqueCombinations);

Answer 5

This is the best that I can do, you need to do your own research to suit your desired result :

const items = [
  { 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" },
  // Add more items for up to 8 slots/spells if needed
];

function groupItemsBySlot(items) {
  return items.reduce((acc, item) => {
    acc[item.slot] = acc[item.slot] || [];
    acc[item.slot].push(item);
    return acc;
  }, {});
}

function generateCombinations(
  groupedItems,
  currentSlotIndex = 0,
  currentCombination = [],
  usedSpells = new Set(),
  allCombinations = []
) {
  const slots = Object.keys(groupedItems);
  if (currentSlotIndex === slots.length) {
    // Base case: all slots processed
    allCombinations.push([...currentCombination]);
    return;
  }

  const currentSlot = slots[currentSlotIndex];
  groupedItems[currentSlot].forEach((item) => {
    if (!usedSpells.has(item.spell)) {
      // Check if the spell is not yet used
      usedSpells.add(item.spell); // Mark the spell as used
      generateCombinations(
        groupedItems,
        currentSlotIndex + 1,
        [...currentCombination, item],
        new Set(usedSpells),
        allCombinations
      );
      usedSpells.delete(item.spell); // Unmark the spell for the next iteration
    }
  });

  if (currentSlotIndex === 0) {
    // Return the result only after the first call completes
    return allCombinations;
  }
}

const groupedItems = groupItemsBySlot(items);
const uniqueCombinations = generateCombinations(groupedItems);
console.log(uniqueCombinations);