Generating all combinations of an array

I’m generating all combinations of an array, so for instance, ["a", "b", "c", "d"] will generate:

[
  "a",    "b",    "ab",   "c",    "ac",
  "bc",   "abc",  "d",    "ad",   "bd",
  "abd",  "cd",   "acd",  "bcd",  "abcd"
]

Here’s the code I’ve written that does complete this task.

What I’d like to know is if there is a better way, as iterating over the array twice feels like I’m cheating, or the complexity of the code is much more computationally expensive than it needs to be.

Also, the name for a function that takes an array and returns the combinations, what might that be called? Combinator seems inappropriate.

var letters = ["a", "b", "c", "d"];
var combi = [];
var temp= "";
var letLen = Math.pow(2, letters.length);

for (var i = 0; i < letLen ; i++){
    temp= "";
    for (var j=0;j<letters.length;j++) {
        if ((i & Math.pow(2,j))){ 
            temp += letters[j]
        }
    }
    if (temp !== "") {
        combi.push(temp);
    }
}

console.log(combi.join("n"));

A recursive solution, originally seen here, but modified to fit your requirements (and look a little more JavaScript-y):

function combinations(str) {
    var fn = function(active, rest, a) {
        if (!active && !rest)
            return;
        if (!rest) {
            a.push(active);
        } else {
            fn(active + rest[0], rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
        return a;
    }
    return fn("", str, []);
}

Test:

combinations("abcd")

Output:

["abcd", "abc", "abd", "ab", "acd", "ac", "ad", "a", "bcd", "bc", "bd", "b", "cd", "c", "d"]

Regarding the name: Don’t name it permutations; a permutation is an arrangement of all the original elements (of which there should be n! total). In other words, it already has a precise meaning; don’t unnecessarily overload it. Why not simply name it combinations?

You can do it recursively:

function getCombinations(chars) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}

Usage:

var combinations = getCombinations(["a", "b", "c", "d"]);

Result:

["a","ab","abc","abcd","abd","ac","acd","ad","b","bc","bcd","bd","c","cd","d"]

I prefer your approach much better than a recursive approach, especially when larger lists are being processed.

Some notes:

• I like the name powerSet as per @200_success
• You do not need to check for combination.length !== 0 if you start with i=1
• If you call the function permutations, then you should not call the list you build combinations, that is confusing
• You could cache list.length, that is a common optimization

With curly braces you can then have:

function powerSet( list ){
    var set = [],
        listSize = list.length,
        combinationsCount = (1 << listSize),
        combination;

    for (var i = 1; i < combinationsCount ; i++ ){
        var combination = [];
        for (var j=0;j<listSize;j++){
            if ((i & (1 << j))){
                combination.push(list[j]);
            }
        }
        set.push(combination);
    }
    return set;
}

without them it could look like this:

function powerSet( list ){
    var set = [],
        listSize = list.length,
        combinationsCount = (1 << listSize);

    for (var i = 1; i < combinationsCount ; i++ , set.push(combination) )
        for (var j=0, combination = [];j<listSize;j++)
            if ((i & (1 << j)))
                combination.push(list[j]);
    return set;
}

An alternative is to build a trie and then walk the trie to generate
the combinations. There are two recursive functions and I’ve timed
it as roughly an order of magnitude slower than your iterative version,
but I thought you might find it interesting nonetheless. (Once JS gets
tail-call optimisation, some recursive approaches will run faster.)

var follows, combinations;

follows = function(a){
    return a.map(function(item, i){
        return [item, follows(a.slice(i+1))];
    });
};

combinations = function(a){
    var combs = function(prefix, trie, result){
        trie.forEach(function(node, i){
            result.push(prefix + node[0]);
            combs(prefix + node[0], node[1], result);
        });
        return result;
    };
    return combs('', follows(a), []);
};

combinations(['a','b','c','d']);

P.S. Your permutations function outputs an array of arrays, not an array of strings like your example at the top of your question. I’ve output an array of strings with my combinations function.

In this case, a non-recursive solution is easier to understand, IMHO:

const powerset = (array) => { // O(2^n)
	const results = [[]];
	for (const value of array) {
		const copy = [...results]; // See note below.
		for (const prefix of copy) {
			results.push(prefix.concat(value));
		}
	}
	return results;
};

console.log(
	powerset(['A', 'B', 'C'])
);

// [ [],
//   [ 'A' ],
//   [ 'B' ],
//   [ 'A', 'B' ],
//   [ 'C' ],
//   [ 'A', 'C' ],
//   [ 'B', 'C' ],
//   [ 'A', 'B', 'C' ] ]

Because results is extended within the loop body, we cannot iterate over it using for-of — doing so would iterate over the newly added elements as well, resulting in an infinite loop. We only want to iterate over the elements that are in results when the loop starts, i.e. indices 0 until results.length - 1. So we either cache the original length in a variable and use that, i.e.

for (let index = 0, length = results.length; index < length; index++) {
    const prefix = results[index];
    // …
}

…or we just create a static copy of results and iterate over that.