Get all possible options for a matrix in javascrip

问题:

I have an 'item' object in JavaScript, and the item can have settings like color, size, etc.

I need to get all possible combinations in an array.

So lets say we have an item that looks like this:

var newItem = {
    name: 'new item',
    Settings: [
        {name: 'color', values: ['green', 'blue', 'red']},
        {name: 'size',  values: ['15', '18', '22']},
        {name: 'gender',values: ['male', 'female']}
    ]
};

I need to somehow get this:

[
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'male'}],
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'15'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'18'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'green'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'blue'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'female'}],
    [{SettingName:'color',value:'red'},{SettingName:'size',value:'22'},{SettingName:'gender',value:'female'}]
]

回答1:

This can be a good interview question.
See JS Bin for running example.

getAllPermutations(newItem);

function getAllPermutations(item) {
    var permutations = [];

    getAllPermutations0(item, permutations, []);
    console.log(permutations);
}

function getAllPermutations0(item, permutations, array) {
    if (array && array.length === item.Settings.length) {
        permutations.push(array.slice()); // The slice clone the array
        return;
    }

    var index =  array.length;
    var setting = item.Settings[index];

    for (var i = 0; i < setting.values.length; i++) {
        if (index === 0)
            array =  [];

        var currValue = setting.values[i];

        array.push({
            SettingName: setting.name,
            value: currValue
        });

        getAllPermutations0(item, permutations, array);
        array.pop(); // pop the old one first
    }
}

回答2:

Here is a none recursive solution. It takes an empty or existing settings "matrix" and a values array, and return a new matrix as a combination of existing matrix content cloned for each new value, appended with pairs of new value setting items.

[A] -> [1,2] gives [A][1][A][2]

[A][1][A][2] -> [X,Y] gives [A][1][X][A][2][Y][A][2][X][A][1][Y]

and so on

function processSettings(settings, name, values) {
  if (settings.length == 0) {
    values.forEach(function(value) {
      settings.push( [{ SettingName: name, value: value }] )
    })
  } else {
    var oldSettings = JSON.parse(JSON.stringify(settings)), settings = [], temp, i = 0
    for (i; i<values.length; i++) {
      temp = JSON.parse(JSON.stringify(oldSettings))
      temp.forEach(function(setting) {
        setting.push( { SettingName: name, value: values[i] } )
        settings.push(setting)
      })
     }
   }
   return settings
}

You can now create the desired settings literal this way :

var settings = []
for (var i=0; i<newItem.Settings.length; i++) {
  var item = newItem.Settings[i]
  settings = processSettings(settings, item.name, item.values)
}

demo -> http://jsfiddle.net/b4ck98mf/

The above produces this :

[
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"male"}],
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"15"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"18"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"green"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"blue"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"female"}],
[{"SettingName":"color","value":"red"},{"SettingName":"size","value":"22"},{"SettingName":"gender","value":"female"}]
]

回答3:

You can use Array.prototype.map(), for loop, while loop, Array.prototype.concat(). Iterate gender values; select each of color, size value in succession beginning at index 0 of either; iterating the furthest adjacent array from current gender, increment the index of the closest adjacent array; merge the resulting two gender arrays to form a single array containing all combinations of gender, color, size

var colors = newItem.Settings[0].values;
var sizes = newItem.Settings[1].values;
var gen = newItem.Settings[2].values;
var i = sizes.length;

var res = [].concat.apply([], gen.map(function(value, key) {
  var next = -1;
  var arr = [];
  for (var curr = 0; curr < i; curr++) {
    while (next < i - 1) {
      arr.push([{
        SettingName: "gender",
        value: value
      }, {
        SettingName: "size",
        value: sizes[curr]
      }, {
        SettingName: "color",
        value: colors[++next]
      }])
    }
    next = -1;
  }
  return arr
}))

var newItem = {
  "name": "new item",
  "Settings": [{
    "name": "color",
    "values": [
      "green",
      "blue",
      "red"
    ]
  }, {
    "name": "size",
    "values": [
      "15",
      "18",
      "22"
    ]
  }, {
    "name": "gender",
    "values": [
      "male",
      "female"
    ]
  }]
}

var colors = newItem.Settings[0].values;
var sizes = newItem.Settings[1].values;
var gen = newItem.Settings[2].values;
var i = sizes.length;

var res = [].concat.apply([], gen.map(function(value, key) {
  var next = -1;
  var arr = [];
  for (var curr = 0; curr < i; curr++) {
    while (next < i - 1) {
      arr.push([{
        SettingName: "gender",
        value: value
      }, {
        SettingName: "size",
        value: sizes[curr]
      }, {
        SettingName: "color",
        value: colors[++next]
      }])
    }
    next = -1;
  }
  return arr
}))

document.querySelector("pre").textContent = JSON.stringify(res, null, 2)

<pre></pre>

plnkr http://plnkr.co/edit/C2fOJpfwOrlBwHLQ2izh?p=preview

回答4:

An approach using Array.prototype.reduce(), Array.prototype.sort(), Object.keys(), for loop, while loop

var newItem = {
    name: 'new item',
    Settings: [
    {
        name: 'color',
        values: ['green', 'blue', 'red']
    }, 
    {
        name: 'size',
        values: ['15', '18', '22']
    }, 
    {
        name: 'gender',
        values: ['male', 'female']
    }
    ]
};

var props = ["SettingName", "value"];
var settings = newItem.Settings;

function p(settings, props) {
var data = settings.reduce(function(res, setting, index) {
  var name = setting.name;
  var obj = {};
  obj[name] = setting.values;
  res.push(obj);
  return res.length < index ? res : res.sort(function(a, b) {
    return a[Object.keys(a)[0]].length - b[Object.keys(b)[0]].length
  })
}, []);
var key = data.splice(0, 1)[0];
return [].concat.apply([], key[Object.keys(key)].map(function(value, index) {
  return data.reduce(function(v, k) {
    var keys = [v, k].map(function(obj) {
      return Object.keys(obj)[0]
    });
    var i = Math.max.apply(Math, [v[keys[0]].length, k[keys[1]].length]);
    var next = -1;
    var arr = [];
    for (var curr = 0; curr < i; curr++) {
      while (next < i - 1) {
        var a = {};
        a[props[0]] = keys[0];
        a[props[1]] = v[keys[0]][++next];
        var b = {};
        b[props[0]] = keys[1];
        b[props[1]] = k[keys[1]][next];
        var c = {};
        c[props[0]] = Object.keys(key)[0];
        c[props[1]] = value;
        arr.push([a, b, c]);
      };
      next = -1;
    }
    return arr
  });
}));
}

document.querySelector("pre").textContent = JSON.stringify(
  p(settings, props), null, 2
);

<pre></pre>