Javascript Question posted in
A very good W3school tutorial can be found here.

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

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!

Tags:

3

Answers


  1. 0

    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)
    Login or Signup to reply.
  2. 0 
    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));
    Login or Signup to reply.
  3. 0

    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);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search