Generate all possible objects from a list of constraints

Question

I am trying to generate all possible object from a constraint hash.

Let's say the constraints are:

{
    key1: [ 'possible value1' , 'possible value2' ],
    key2: [ 2, 4, 7, 1],
    ...
}

And I want to produce all the possible objects:

{ key1: 'possible value1', key2: 2 }

{ key1: 'possible value1', key2: 4 }

...

Anyone could point me in the right direction ?

Thank you !

See [Generating combinations from n arrays with m elements](http://stackoverflow.com/q/15298912/1048572). In your case, they're object properties, but that doesn't make a difference — Bergi, May 15 '17 at 05:32

Keshan Nageswaran · Accepted Answer · 2017-05-15T05:06:28.647

var options = {
        key1: [ 'possible value1' , 'possible value2'],
        key2: [ 2, 4, 7, 1],
        key3: ['TEST1', 'TEST2']
};

function getCombinations(options, optionIndex, results, current) {
    var allKeys = Object.keys(options);
    var optionKey = allKeys[optionIndex];

    var vals = options[optionKey];

    for (var i = 0; i < vals.length; i++) {
        current[optionKey] = vals[i];

        if (optionIndex + 1 < allKeys.length) {
            getCombinations(options, optionIndex + 1, results, current);
        } else {
            var res = JSON.parse(JSON.stringify(current));
            results.push(res);
        }
    }

    return results;
}

var results = getCombinations(options, 0, [], {});

document.body.innerHTML = JSON.stringify(results);

Amadan · Answer 2 · 2017-05-15T05:20:31.270

let constraints = {
  key1: ['possible value1' , 'possible value2'],
  key2: [2, 4, 7, 1],
  key3: ["foo", "bar"],
};

let result = Object.keys(constraints).reduce(
  (acc, key) =>
    acc.map(a1 =>
      constraints[key].map(a2 =>
        a1.concat([a2])
      )
    ).reduce((e1, e2) => e1.concat(e2)),
  [[]]
);

console.log(JSON.stringify(result));

First we make sure we know how to make all concatenations of elements of two arrays, if the first contains arrays (all arrays produced by some set of constraints) and the second single elements (a new constraint). (e.g. [["possible value1"], ["possible value2"] and [1, 2]). We map one array, map the other array, then stick them together (the a1 and a2 maps, a1.concat([a2])). The nested map will produce a two-level array, so we'll just concatenate all arrays from the single level (the inner reduce).

Note that if we concatenate an empty array to an array, the array is unchanged; thus, we could introduce another constraint, an empty one: []. If we combine all the arrays that correspond to this constraint, [[]], with ["possible value1", "possible value2"], we still get the same set. This is the starting value for our outer reduce: starting with this "null element", we can concatenate other constraints as described above.

EDIT: made prettier:

let constraints = {
  key1: ['possible value1' , 'possible value2'],
  key2: [2, 4, 7, 1],
  key3: ["foo", "bar"],
};

const unconstrainedPossibilities = [[]];

const flatten = array => array.reduce((a1, a2) => a1.concat(a2));

const addConstraint = (possibilities, constraint) =>
  flatten(
    possibilities.map(possibility =>
      constraint.map(constraintValue =>
        possibility.concat([constraintValue])
      )
    )
  );

const possibilitiesFor = constraints =>
  constraints.reduce(
    (possibilities, constraint) => addConstraint(possibilities, constraint),
    unconstrainedPossibilities
  );

let possibilities = possibilitiesFor(Object.values(constraints));
console.log(JSON.stringify(possibilities));

score 0 · Answer 3 · answered May 15 '17 at 05:43

I know there are more elegant ways to do this, but I wanted to come up with an algorithm that didn't really involve much thinking, so, my idea was just to use a basic while loop where each iteration of the loop creates the next combination and sticks it in an output array.

I start by creating a keys array that contains an object for each key in the form {k: "key1", index: 0, length: 2} - basically to keep track for that key which index we're up to in its array, and how long its array is. Then the first line of the while loop uses .reduce() to build an object with the values from the current indices of each key, and then uses a for loop to move to the next combination. When it gets to the end of the combinations it breaks out of the while loop.

const constraints = {
  key1: ['pv1', 'pv2', 'pv3', 'pv4'],
  key2: [2, 4, 7, 1],
  key3: ['a', 'b'],
  key4: [10, 20, 30]
}

const output = []

const keys = Object.keys(constraints)
  .map(k => ({ k: k, index: 0, length: constraints[k].length }))

process: while (true) {
  output.push(keys.reduce((a, c) => {
    a[c.k] = constraints[c.k][c.index];
    return a;
  }, {}))

  for (let i = keys.length - 1; i >= 0; i--) {
    keys[i].index++
    if (keys[i].index < keys[i].length) break
    if (i === 0) break process
    keys[i].index = 0
  }
}

console.log(JSON.stringify(output))

Generate all possible objects from a list of constraints

3 Answers3