I have the following JavaScript object structure:

var options = {
    optionOne: [true, false],
    optionTwo: [true, false],
    optionThree: [
        null,
        {property1: 9, property2: 7},
        {property1: 4, property2: 12},
        {property1: 16, property2: 14}
    ]
};

Please note that the number of key/pairs in this object will differ. So there might actually be optionFour, optionFive, etc., and each option can have any number or type of values for its array.

I need to iterate through this object and create an array containing objects of all possible option combinations:

[
    {optionOne: true,  optionTwo, true,  optionThree: null},
    {optionOne: false, optionTwo, true,  optionThree: null},
    {optionOne: true,  optionTwo, false, optionThree: null},
    {optionOne: false, optionTwo, false, optionThree: null},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 9, property2: 7}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 9, property2: 7}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 9, property2: 7}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 9, property2: 7}},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 4, property2: 12}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 4, property2: 12}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 4, property2: 12}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 4, property2: 12}},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 16, property2: 14}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 16, property2: 14}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 16, property2: 14}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 16, property2: 14}}
]

I'm struggling on how to accomplish this but am fairly confident the answer lies in recursion.

Can the algorithm gods help me?

I have the following JavaScript object structure:

var options = {
    optionOne: [true, false],
    optionTwo: [true, false],
    optionThree: [
        null,
        {property1: 9, property2: 7},
        {property1: 4, property2: 12},
        {property1: 16, property2: 14}
    ]
};

Please note that the number of key/pairs in this object will differ. So there might actually be optionFour, optionFive, etc., and each option can have any number or type of values for its array.

I need to iterate through this object and create an array containing objects of all possible option combinations:

[
    {optionOne: true,  optionTwo, true,  optionThree: null},
    {optionOne: false, optionTwo, true,  optionThree: null},
    {optionOne: true,  optionTwo, false, optionThree: null},
    {optionOne: false, optionTwo, false, optionThree: null},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 9, property2: 7}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 9, property2: 7}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 9, property2: 7}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 9, property2: 7}},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 4, property2: 12}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 4, property2: 12}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 4, property2: 12}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 4, property2: 12}},
    {optionOne: true,  optionTwo, true,  optionThree: {property1: 16, property2: 14}},
    {optionOne: false, optionTwo, true,  optionThree: {property1: 16, property2: 14}},
    {optionOne: true,  optionTwo, false, optionThree: {property1: 16, property2: 14}},
    {optionOne: false, optionTwo, false, optionThree: {property1: 16, property2: 14}}
]

I'm struggling on how to accomplish this but am fairly confident the answer lies in recursion.

Can the algorithm gods help me?

• javascript
• algorithm
• recursion
• combinations
• permutation

• 3 how about this - stackoverflow.com/questions/4331092/… – Joe Hanink Commented Sep 29, 2015 at 8:10
• 1 HA -- that's exactly the one I've been looking at for the past hour and trying to model :) – Chad Johnson Commented Sep 29, 2015 at 8:12

4 Answers 4

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 {
            // The easiest way to clone an object.
            var res = JSON.parse(JSON.stringify(current));
            results.push(res);
        }
    }

    return results;
}

Use it like this:

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

Here's a working JSFiddle example.

This was recently resurrected, and I think modern JS offers a cleaner way to write this.

const crossproduct = (xss) => 
  xss.reduce((xs, ys) => xs.flatMap(x => ys.map(y => [...x, y])), [[]])

const combinations = (o, keys = Object .keys (o), vals = Object .values (o)) =>
  crossproduct(vals).map(xs => Object.fromEntries(xs.map ((x, i) => [keys[i], x])))


const options = {optionOne: [true, false], optionTwo: [true, false], optionThree: [null, {property1: 9, property2: 7}, {property1: 4, property2: 12}, {property1: 16, property2: 14}]}

console .log (JSON .stringify (
  combinations (options)
, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

We start with a crossproduct function which, for instance, takes

[[1, 2], ['a', 'b', 'c'], ['T', 'F']]

and returns

[
  [1, 'a', 'T'], [1, 'a', 'F'], [1, 'b', 'T'], [1, 'b', 'F'], [1, 'c', 'T'], [1, 'c', 'F'], 
  [2, 'a', 'T'], [2, 'a', 'F'], [2, 'b', 'T'], [2, 'b', 'F'], [2, 'c', 'T'], [2, 'c', 'F']
]

Then combinations takes our object apart with Object.keys, and Object.values, passes the values to crossproduct, then for each array in the result, maps over the values, associating the corresponding key with each, then rehydrating an object with Object.fromEntries.

This order is what seems like the logical order of results to me. But if we swapped out the returned expression for crossproduct with the following, we would get the order mentioned in the question:

  xss .reduce ((xs, ys) => ys .flatMap (y => xs .map (x => [...x, y])), [[]])

Here is an improvement, based on Dmytro's answer:

function getPermutations(object, index = 0, current = {}, results = []) {
  const keys = Object.keys(object);
  const key = keys[index];
  const values = object[key];

  for (const value of values) {
    current[key] = value;
    const nextIndex = index + 1;

    if (nextIndex < keys.length) {
      this.getPermutations(object, nextIndex, current, results);
    } else {
      const result = Object.assign({}, current);
      results.push(result);
    }
  }
  return results;
}

Improvements:

• Works for any kind of value, even if the value is a function
• Default argument values, can be easily invoked with: const p = getPermutations(object);
• Minor semantic improvements

For anyone seeking a TypeScript based answer:

export function getCartesian<TOut extends Record<string, unknown[]>>(inputObject: TOut): Array<{ [K in keyof TOut]: TOut[K][number] }> {
// Reduce the entries of the input object to generate the Cartesian product
return Object.entries(inputObject).reduce((accumulator, [key, valuesArray]) => {
    const combinations: Array<{ [K in keyof TOut]: TOut[K][number] }> = [];
    
    accumulator.forEach(existingCombination => {
        valuesArray.forEach(singleValue => {
            // If the value is an object, recursively get its Cartesian product
            const nestedValues = (singleValue && typeof singleValue === 'object' && !Array.isArray(singleValue)) 
                ? getCartesian(singleValue as Record<string, unknown[]>) 
                : [singleValue];
            
            // Combine the existing combination with each nested value
            nestedValues.forEach(nestedValue => {
                combinations.push({ ...existingCombination, [key]: nestedValue });
            });
        });
    });
    
    return combinations;
}, [{} as { [K in keyof TOut]: TOut[K][number] }]);

}