如何在JavaScript中按元素权重规则生成全部组合集合

核心思路说明 #

需求本质是保证每个层级内的元素，在最终生成的所有组合中出现的占比严格等于它的权重值（权重1就是出现1%）。以下提供两种常用实现方案，匹配不同使用场景：

方案1：固定100个组合，严格匹配权重 #

适用于需要生成固定数量组合、每个元素出现次数完全等于权重的场景，刚好匹配你示例中combTotal=100的需求。

实现步骤： #

• 先校验每个层级的权重总和为100（你示例中第三个层级权重总和为99，需要补1的差值调整为100）
• 对每个层级生成打乱的元素序列：将层级内的元素按权重值重复对应次数，再随机打乱序列，每个层级最终得到长度为100的序列
• 按索引取各层级的元素拼接为组合，第i个组合为[层1序列[i], 层2序列[i], 层3序列[i]]，最终刚好得到100个符合要求的组合

代码实现： #

// 工具函数：打乱数组
function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

// 生成每个层级的打乱序列
function generateLayerSeq(layer) {
  const seq = []
  layer.forEach(item => {
    // 按权重重复元素
    for(let i=0; i<item.weight; i++) {
      seq.push(item.id)
    }
  })
  return shuffle(seq)
}

// 生成最终组合
function generateCombinations(layers) {
  const layerSeqs = layers.map(layer => generateLayerSeq(layer))
  const total = layerSeqs[0].length
  const result = []
  for(let i=0; i<total; i++) {
    const comb = layerSeqs.map(seq => seq[i])
    result.push(comb)
  }
  return result
}

// 调用示例
const result = generateCombinations(layers)
console.log(result)

方案2：任意数量随机生成，统计符合权重 #

适用于需要生成任意数量组合、不需要严格固定出现次数、仅要求长期统计上符合权重占比的场景。

实现步骤： #

• 预处理每个层级的前缀和权重表，用于快速加权随机采样
• 每次生成组合时，对每个层级单独生成1-100的随机数，匹配前缀和表找到对应元素
• 多次生成后，每个元素的出现占比会趋近于它的权重值

代码实现： #

// 预处理层级的前缀和表
function preprocessLayer(layer) {
  const prefixSum = []
  let sum = 0
  layer.forEach(item => {
    sum += item.weight
    prefixSum.push({sum, id: item.id})
  })
  return prefixSum
}

// 单层级加权随机取元素
function getRandomItem(prefixSum) {
  const rand = Math.random() * 100
  for(let item of prefixSum) {
    if(rand <= item.sum) return item.id
  }
  return prefixSum[prefixSum.length - 1].id
}

// 生成指定数量的组合
function generateRandomCombs(layers, count) {
  const processedLayers = layers.map(layer => preprocessLayer(layer))
  const result = []
  for(let i=0; i<count; i++) {
    const comb = processedLayers.map(layer => getRandomItem(layer))
    result.push(comb)
  }
  return result
}

// 调用示例：生成200个符合权重的组合
const result = generateRandomCombs(layers, 200)
console.log(result)

注意点 #

• 如果层级数量更多，上述两种方案都可以直接兼容，不需要修改逻辑
• 若权重总和不是100，可以先将权重归一化处理后再使用，逻辑不变

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