sku排列组合

2022-05-21 18:15  1401人阅读  评论 (0)

使用栈实现

function combination1(opts) {
  if (opts.length === 0 || opts.some(v => v.length === 0)) { throw new Error('opts error!'); }
  const items = [], i = opts.map(_ => 0);
  while (true) {
    if (i[i.length-1] >= opts[i.length-1].length) {
      i.pop();
      if (i.length === 0) { return items; }
      i[i.length-1]++;
    } else if (i.length < opts.length) {
      i.push(0);
    } else {
      items.push(i.map((k, j) => opts[j][k]));
      i[i.length-1]++;
    }
  }
  return items; // unreachable
}

使用进位实现

function combination2(opts) {
  if (opts.length === 0 || opts.some(v => v.length === 0)) { throw new Error('opts error!'); }
  let items = [], i = opts.map(_ => 0), e = opts.length - 1, c = 0;
  while (true) {
    items.push(i.map((k, j) => opts[j][k]));
    i[e]++;
    c = e;
    while (i[c] >= opts[c].length) { // carry
      i[c] = 0;
      if (c <= 0) return items; // overflow
      i[--c]++;
    }
  }
  return s; // unreachable
}

使用进制转换实现

function combination3(opts) {
  if (opts.length === 0 || opts.some(v => v.length === 0)) { throw new Error('opts error!'); }
  let items = [], b = opts.map(v => v.length);
  for (let e = b.reduceRight((a, c) => a * c, 1), j = 0; j < e; j++) {
    const i = [...b];
    for (let n = j, k = i.length-1; k >= 0; k--) {
      i[k] = n % b[k];
      n = n / b[k] | 0;
    }
    items.push(i.map((k, j) => opts[j][k]));
  }
  return items;
}

测试

const opts = [
  ["1","2","3"],
  ["a","b","c","d"],
  ["一","二","三"],
  ["甲","已","丙", "丁"],
];
console.log(combination1(opts).map(v => v.join('\t')).join("\n"));
console.log(combination2(opts).map(v => v.join('\t')).join("\n"));
console.log(combination3(opts).map(v => v.join('\t')).join("\n"));
豫ICP备09035262号-1