javascript中对象的笛卡尔积 [英] Cartesian product of objects in javascript

问题描述

我需要根据N个属性列表生成一组完整的变体，同时保持属性名称不变。

I need to generate a complete set of variants based on a list of N attributes, while keeping the attribute name intact.

var input = [
    { 'colour' : ['red', 'green'] },
    { 'material' : ['cotton', 'wool', 'silk'] },
    { 'shape' : ['round', 'square', 'rectangle'] }
];

var expected = [
    { 'colour': 'red', 'material': 'cotton', 'shape': 'round' },
    { 'colour': 'red', 'material': 'cotton', 'shape': 'square' },
    { 'colour': 'red', 'material': 'cotton', 'shape': 'rectangle' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'round' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'square' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'rectangle' },
    { 'colour': 'red', 'material': 'silk', 'shape': 'round' },
    { 'colour': 'red', 'material': 'silk', 'shape': 'square' },
    { 'colour': 'red', 'material': 'silk', 'shape': 'rectangle' },
    { 'colour': 'green', 'material': 'cotton', 'shape': 'round' },
    { 'colour': 'green', 'material': 'cotton', 'shape': 'square' },
    { 'colour': 'green', 'material': 'cotton', 'shape': 'rectangle' },
    { 'colour': 'green', 'material': 'wool', 'shape': 'round' },
    { 'colour': 'green', 'material': 'wool', 'shape': 'square' },
    { 'colour': 'green', 'material': 'wool', 'shape': 'rectangle' },
    { 'colour': 'green', 'material': 'silk', 'shape': 'round' },
    { 'colour': 'green', 'material': 'silk', 'shape': 'square' },
    { 'colour': 'green', 'material': 'silk', 'shape': 'rectangle' }
];

对于阵列的笛卡尔积，有很多算法，但我似乎找不到一个对于保留密钥的对象。

There are lots of algorithms around for cartesian products of arrays, but I can't seem to find one for objects that preserves the keys.

性能不是一个大问题，因为每个属性永远不会有超过十几个值。订单不必完全匹配预期。

Performance isn't a massive concern as there will never be more than a dozen or so values for each attribute. The order doesn't have to exactly match expected.

我已根据标准进行了初步尝试列表算法，但我很挣扎：

I've made an initial attempt based on the standard algorithms for lists, but I'm struggling:

function cartesianProduct(input, current) {
    if (!input || input.length < 1) {
        return [];
    }

    var head = input[0];
    var tail = input.slice(1);
    var output = [];

    for (var key in head) {
        for (var i = 0; i < head[key].length; i++) {
            if (typeof current == 'undefined') {
                var current = {};
            }

            current[key] = head[key][i];
            var productOfTail = cartesianProduct(tail, current);
            output.push(current);
            console.log(current);
        }
    }

    return output;
}

console.log(cartesianProduct(input));

推荐答案

一旦你摆脱''我'是一个全局变量问题'，您可以使用以下代码获得结果：

Once you get rid of the ' 'i' is a global var issue', you can get to the result with this code for instance :

var input = [
    { 'colour' : ['red', 'green'] },
    { 'material' : ['cotton', 'wool', 'silk'] },
    { 'shape' : ['round', 'square', 'rectangle'] }
];

function cartesianProduct(input, current) {
   if (!input || !input.length) { return []; }

   var head = input[0];
   var tail = input.slice(1);
   var output = [];

    for (var key in head) {
      for (var i = 0; i < head[key].length; i++) {
            var newCurrent = copy(current);         
            newCurrent[key] = head[key][i];
            if (tail.length) {
                 var productOfTail = 
                         cartesianProduct(tail, newCurrent);
                 output = output.concat(productOfTail);
            } else output.push(newCurrent);
       }
     }    
    return output;
}

function copy(obj) {
  var res = {};
  for (var p in obj) res[p] = obj[p];
  return res;
}


console.log(cartesianProduct(input));

这篇关于javascript中对象的笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！