sku排列组合
2022-05-21 18:15
1174人阅读
评论 (0)
Tags: skucombination
使用栈实现
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"));