如何生成对象数组基于slot与spell属性的所有唯一组合

给定一个对象数组，需要生成所有满足以下条件的唯一组合：

• 每个组合包含不同slot的item
• 组合内所有item的spell无重复

示例输入 #

[
  { 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' },
]

理想输出 #

每个组合包含不同slot的item，且spell无重复：

[
  [
    { 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 str1' },
    { slot: 'legs', spell: 'dexterity.i', item: 'legs dex1' },
    { slot: 'head', spell: 'combat.i', item: 'head combat1' },
  ],
  // ... 其他符合条件的组合
]

已完成的预处理 #

已编写generateList函数将数据按slot和spell分类，生成结构化数据：

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

预处理后的数据结构 #

{
  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' } ]
  }
}

解决方案 #

核心思路 #

问题拆解为两步：

1. 生成所有slot与spell的唯一映射排列：即每个slot对应一个唯一的spell，所有spell不重复（本质是spell数组的全排列，每个排列对应slot的分配）
2. 对每个映射排列，计算各slot对应spell下item列表的笛卡尔积，得到该映射下的所有具体组合

代码实现 #

1. 生成slot-spell唯一映射排列

递归生成所有合法的slot到spell的映射（确保每个spell只被用一次）：

// 生成所有slot到spell的唯一映射排列
function generateSpellAssignments(slots, effects, usedEffects = [], current = {}) {
  if (Object.keys(current).length === slots.length) {
    return [current];
  }
  const results = [];
  const currentSlot = slots[Object.keys(current).length];
  for (const effect of effects) {
    if (!usedEffects.includes(effect)) {
      results.push(...generateSpellAssignments(
        slots,
        effects,
        [...usedEffects, effect],
        {...current, [currentSlot]: effect}
      ));
    }
  }
  return results;
}

2. 计算多数组的笛卡尔积

用于扩展每个slot下对应spell的item列表：

// 计算多个数组的笛卡尔积
function cartesianProduct(arrays) {
  return arrays.reduce((acc, curr) => {
    return acc.flatMap(a => curr.map(c => [...a, c]));
  }, [[]]);
}

3. 整合生成最终组合

结合预处理数据、映射排列和笛卡尔积，生成所有符合要求的组合：

function generateValidCombinations(preprocessedData, slots, effects) {
  // 生成所有合法的slot-spell映射
  const assignments = generateSpellAssignments(slots, effects);
  const allCombinations = [];

  for (const assignment of assignments) {
    // 收集每个slot对应spell的item列表
    const itemLists = slots.map(slot => preprocessedData[slot][assignment[slot]]);
    // 过滤掉空列表的情况（如果某个slot没有对应spell的item）
    if (itemLists.every(list => list.length > 0)) {
      // 计算笛卡尔积，得到该映射下的所有组合
      const product = cartesianProduct(itemLists);
      allCombinations.push(...product);
    }
  }

  return allCombinations;
}

4. 使用示例

// 原始输入数据
const inputData = [/* 你的输入数组 */];
const slots = ['body', 'legs', 'head'];
const effects = ['combat.i', 'strength.i', 'dexterity.i'];

// 预处理数据
const preprocessed = generateList(inputData, slots, effects);
// 生成所有合法组合
const result = generateValidCombinations(preprocessed, slots, effects);
console.log(result);

大规模数据优化建议 #

如果数据量较大，递归可能导致栈溢出，且一次性生成所有组合会占用大量内存，可以做以下优化：

• 迭代代替递归：将generateSpellAssignments改为迭代实现，避免栈溢出
• 使用生成器函数：将generateValidCombinations改为生成器，通过yield逐个返回组合，减少内存占用
• 提前过滤无效映射：在生成映射排列时，提前判断slot是否有对应spell的item，跳过无效映射，减少计算量

内容的提问来源于stack exchange，提问作者larz