Calculate all possible combinations of an array of arrays or strings

Question

I'm using code adapted from this Stack Overflow question to calculate all possible combinations from an array, which may contains strings.

For example:

[ "x", "y", "z" ] => "x y z"
[ [ "a", "b"] , "c", "d" ] => [ "a c d", "b c d" ]
[ [ "a", "b"] , ["c" "d"], "e"] => [ "a c e", "b c e", "a d e", "b d e" ]

However as the items could be strings or array I need to check for all possible combinations of array/string pairs when building the results.

This has ended in rather messy code, and I'd appreciate any hints on how to tidy it up. I've attempted to refactor it, but I guess I'm tired and missing something!

function allPossibleCases(arr) {
  if (arr.length === 0) {
    return [];
  } 
  else if (arr.length === 1){
    return arr[0];
  }
  else {
    var result = [];
    var allCasesOfRest = allPossibleCases(arr.slice(1));  // recur with the rest of array

    if(typeof allCasesOfRest === 'string') {
      if(typeof arr[0] === 'string') {
          result.push(arr[0] + " " + allCasesOfRest);
      } else {    
        for (var i = 0; i < arr[0].length; i++) {
            result.push(arr[0][i] + " " + allCasesOfRest);
        }
      }
    }

    else {
      for (var c in allCasesOfRest) {
        if(typeof arr[0] === 'string') {          
          result.push(arr[0] + " " + allCasesOfRest[c]);
        } else {
          for (var i = 0; i < arr[0].length; i++) {
            result.push(arr[0][i] + " " + allCasesOfRest[c]);
          }
        }
      }
    }
    return result;
  }

}

Answer 1

1. You don't need the else if/else blocks at the top; it can just be if blocks, since they return and thus exit the function anyway.

   if (arr.length === 0) {
     return []; // stop here
   } 
   
   if (arr.length === 1){
     return arr[0]; // or here
   }
   
   // or continue with the rest of the function
   

2. As you yourself noted, normalize the input, so you don't need to be type-checking inside the loop

But I'd advice you ignore that you're dealing with strings specifically, and just worry about "combinations of stuff", and try for a generic solution.

Still, the manual array-building makes your code cryptic. I'd suggest a more functional approach, using map and reduce.

Not saying it's easier to follow at first glance, but there's less code, and it's generic:

// this produces a 2d array of combinations
function combinations(array) {
  if(!array.length) {
    return [];
  }

  // wrap non-array values
  // e.g. ['x',['y','z']] becomes [['x'],['y','z']]
  array = array.map(function (item) {
    return item instanceof Array ? item : [item];
  });

  // internal recursive function
  function combine(list) {
    var prefixes, combinations;

    if(list.length === 1) {
      return list[0];
    }

    prefixes = list[0];
    combinations = combine(list.slice(1)); // recurse

    // produce a flat list of each of the current
    // set of values prepended to each combination
    // of the remaining sets.
    return prefixes.reduce(function (memo, prefix) {
      return memo.concat(combinations.map(function (combination) {
        return [prefix].concat(combination);
      }));
    }, []);
  }

  return combine(array);
}

To convert the output of the above function to strings, just add another map call:

function allPossibleCases(arr) {
  return combinations(arr).map(function (combination) {
    return combination.join(" ");
  });
}

You get this:

[ 'x', 'y', 'z' ]                   => [ 'x y z' ]
[ [ 'a', 'b' ], 'c', 'd' ]          => [ 'a c d', 'b c d' ]
[ [ 'a', 'b' ], [ 'c', 'd' ], 'e' ] => [ 'a c e', 'a d e', 'b c e', 'b d e' ]

Note that the order of the last one is different from yours, though it contains the same combinations.

Answer 2

You could do it something like this:

function allPossibleCases(array, result, index) { 
    if (!result) {
        result = [];
        index = 0;
        array = array.map(function(element) {
            return element.push ? element : [element]; 
        });
    }
    if (index < array.length) {
        array[index].forEach(function(element) {
            var a = array.slice(0);
            a.splice(index, 1, [element]);
            allPossibleCases(a, result, index + 1);
        });
    } else {
        result.push(array.join(' '));
    }

    return result;
}

When you call the function, the first if clause sets up values for the result and index arguments used for recursive calls (so you don't need to pass those arguments). It also creates a normalized copy of the array, wrapping strings in single-element arrays.

The second if clause checks that we haven't reached the end of the array, and calls the function recursively, once for each member of the internal array at this index. Or, if we have reached the end of the array, push a result onto the array we return.

Try it:

var t1 = ["x", "y", "z"];
var t2 = [["a", "b"], "c", "d"];
var t3 = [["a", "b"], ["c", "d"], "e"];

console.log(allPossibleCases(t1)); // ["x y z"] 
console.log(allPossibleCases(t2)); // ["a c d", "b c d"] 
console.log(allPossibleCases(t3)); // ["a c e", "a d e", "b c e", "b d e"]

I would definitely recommend looking at this answer on the question you linked, though. If you can deal with the sets one at a time, that's a better way to go.