多规格多维数组匹配怎么循环

Question

// 需要解决的问题
例1
let sizes = ['x', 'xl'];
let colors =['黑', '白', '灰'];
let czs = ['棉', '涤纶'];
let heights = ['170cm', '180cm'];
let arr = [];
for(let size of sizes) {
    for(let color of colors) {
        for(let cz of czs) f
            for(let height of heights) {
                arr.push({item: `${size}-${color}-${cz}-${height}`});
            }
        }
    }
}

// 例2 怎么实现像上面那样的效果
let specs = [
    ['x', 'xl'],
    ['黑', '白', '灰'],
    ['棉', '涤纶'],
    ['170cm', '180cm'],
]

Answer 1

const specs = [
    ["x", "xl"],
    ["黑", "白", "灰"],
    ["绵", "涤纶"],
    ["170cm", "180cm"]
];

const result = specs
    .reduce((rList, arr) => arr.flatMap(it => rList.map(r => [...r, it])), [[]])
    .map(it => it.join("-"));
console.log(result);

[
  'x-黑-绵-170cm',   'xl-黑-绵-170cm',
  'x-白-绵-170cm',   'xl-白-绵-170cm',
  'x-灰-绵-170cm',   'xl-灰-绵-170cm',
  'x-黑-涤纶-170cm', 'xl-黑-涤纶-170cm',
  'x-白-涤纶-170cm', 'xl-白-涤纶-170cm',
  'x-灰-涤纶-170cm', 'xl-灰-涤纶-170cm',
  'x-黑-绵-180cm',   'xl-黑-绵-180cm',
  'x-白-绵-180cm',   'xl-白-绵-180cm',
  'x-灰-绵-180cm',   'xl-灰-绵-180cm',
  'x-黑-涤纶-180cm', 'xl-黑-涤纶-180cm',
  'x-白-涤纶-180cm', 'xl-白-涤纶-180cm',
  'x-灰-涤纶-180cm', 'xl-灰-涤纶-180cm'
]

---

答案是给了，还是讲下思路吧。

简单的说就是遍历数组，每组数据与之前的结果“相乘”（笛卡尔积）。比如

["x", "xl"] 与 ["黑", "白", "灰"] 的乘积是：

[["x", "黑"], ["xl", "黑"], ["x", "白"], ["xl", "白"], ["x", "灰"], ["xl", "灰"]]

这里如果我们把 ["x", "xl"] 看成是 [["x"], ["xl"]] 就会发现，被乘集和结果集是一样的结构，都是二维数组，每次乘一个新的集合，只是把被乘集拷贝 n（n 是新数组长度）份，每份依次加入新集合的元素，最后把结果展平（合并）。

比如对上面的集合再乘个 ["170cm", "180cm"]，

① 先把原结果集元素拷贝成 2 份（新数组长度）

❶ [["x", "黑"], ["xl", "黑"], ["x", "白"], ["xl", "白"], ["x", "灰"], ["xl", "灰"]],
❷ [["x", "黑"], ["xl", "黑"], ["x", "白"], ["xl", "白"], ["x", "灰"], ["xl", "灰"]]

再依次加入新元素，第 ❶ 份加 170cm，第 ❷ 份加 180cm

❶ [["x", "黑", "170cm"], ["xl", "黑", "170cm"], ["x", "白", "170cm"], ["xl", "白", "170cm"], ["x", "灰", "170cm"], ["xl", "灰", "170cm"]],
❷ [["x", "黑", "180cm"], ["xl", "黑", "180cm"], ["x", "白", "180cm"], ["xl", "白", "180cm"], ["x", "灰", "180cm"], ["xl", "灰", "180cm"]]

最后 flat 一层（合并两个二维数组）得到

[
    ["x", "黑", "170cm"], ["xl", "黑", "170cm"],
    ["x", "白", "170cm"], ["xl", "白", "170cm"],
    ["x", "灰", "170cm"], ["xl", "灰", "170cm"], // 这之前是❶中的，之后是❷中的
    ["x", "黑", "180cm"], ["xl", "黑", "180cm"],
    ["x", "白", "180cm"], ["xl", "白", "180cm"],
    ["x", "灰", "180cm"], ["xl", "灰", "180cm"]
]

依次循环下去，就能拿到最后的结果。当然最后结果的每个元素都是一个包含了各项规格的数组。再用 join 把元素连接起来成一个字符串就是最终结果，这步比较简单，算后期处理了。

问题是，既然是循环，那循环体就应该有一致性。简单说就是每次处理的输入输出是一致的（递归也是这个思想）。在乘第一个数组，就是 ["x", "xl"] 那个的时候，没有被乘集，我们应该初始化一个出来。这个集合肯定不是能空的（从数学的思想来看， 0 乘以任何数都是 0），所以这个初始集合应该是 [[]]。这个集合有一个元素，这个元素是个空集合（因为后面是往里 + 规格，不再是乘，所以可空）

整个过程用循环来写就是

let result = [[]];
for (const arr of specs) {
    const groups = arr.map(it => {
        // 对 arr 中的每个元素，拷贝一份 result， 这个拷贝也是一个二维数组
        const copy = [...result];
        // 对其每个元素（数组）拷贝并添加 it
        return copy.map(el => [...el, it]);
    });
    result = groups.flat();
}
// 对结果进行加工（使用 - 连接成字符串）
result = result.map(it => it.join("-"));
console.log(result);

这个循环可以改写成 reduce；拷贝过程可以用 map 代替，flat 和 map 可以合并成 flatMap，再把最后的处理过程连接上去，就得到了上面的答案。

---

再补充两个递归的写法：

1) 是把结果集作为输出参数传入递归（封装了 IIFE，所以外部接口不需要准备输出参数）

// 使用 IIFE 把递归逻辑封装起来，简化调用接口
const flatSpecs = (() => {
    function combine(result, specs, level = 0, prev = []) {
        if (level === specs.length) {
            result.push(prev);
            return;
        }
        specs[level].forEach(spec => combine(result, specs, level + 1, [...prev, spec]));
    }

    return function (specs) {
        const result = [];
        combine(result, specs);
        return result.map(arr => arr.join("-"));
    };
})();

console.log(flatSpecs(specs));

2) 每轮直接返回结果

由于每轮输入集合数量与输出数量不等（是展开关系），不能直接用 map，需要使用 flatMap

这种方式通过可选参数能提供简化后的调用接口。但是如果想限制用户不乱输入后面两个参数，最好还是再用 IIFE 封一下。

function combine(specs, level = 0, prev = []) {
    if (level === specs.length) {
        return [prev];
    }
    return specs[level].flatMap(spec => combine(specs, level + 1, [...prev, spec]));
}

console.log(combine(specs).map(arr => arr.join("-")));

Answer 2

const combine = (specs, opt = {}, i = 0, res = [], pre = "") => {
  if (i === specs.length) res.push(typeof opt.fn === "function" ? opt.fn(pre) : pre)
    else specs[i].forEach(s => (
        combine(specs, opt, i + 1, res, pre + (i ? opt.div ?? "-" : "") + s)
    ))
    if (! i) return res
}

combine([['x','xl'], ['黑','白','灰']], { fn: s => ({ item: s }) })

Answer 3

function transform(arr) {
    return (function collect(result, depth, cache) {
        var list = arr[depth++];
        for (var i = 0; i < list.length; ++i) {
            var values = cache.concat([list[i]]);
            if (depth < arr.length) {
                collect(result, depth, values);
            } else {
                result.push(values.join());
            }
        }
        return result;
    })([], 0, []);
}
console.dir(transform(specs));

Answer 4

其实这个还有一种算法，就是位段划分法，其思路是，无论单独标准有多少规格，其对应数量必然可以映射到多位二进制数中，比如有两种规格，可以用1位二进制数来表示，如果是3种或者4种，则需要用2位二进制数来表示，这样多个分别对应类型的位段按一定规律可以组合出有限位的二进制数。这样无论多少规格的全组合，肯定可以映射到一个多位二进制数中。再筛除掉任何一个位段不存在的标准规则，比如 有个标准 有3个规格，则有效的规格是00、01、10，而没有11，剩余的必然是所有可能的全组合。

这里，对于标准只有1个规格的可以预先提取出来，减少组合处理。