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"));
up vote 45 down vote accepted

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?

  • Stumbled back here and have no idea why I didn't originally point out that "combination" also has an existing mathematical definition en.wikipedia.org/wiki/Combination – Wayne Burkett Nov 10 '13 at 6:41
  • 5
    "All possible combinations" can also be called a "power set". – 200_success Jan 2 '14 at 17:28
  • 3
    On closer inspection… a power set should include the empty string. I'm not sure what to call a power set minus the empty string. – 200_success Jan 21 '14 at 17:24
  • 1
    I'm trying to create my library of babel and this came in handy xD – Kyle Oct 1 '15 at 11:36
  • Instead of "power set" (which is about sets, without caring for order), an even better name would be subsequences (although technically that includes the empty sequence as well). – Bergi Jul 31 '16 at 23:24

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;
}
  • 1
    The first version is excellent. The second one is not nearly as good. – 200_success Jan 21 '14 at 17:21
  • 3
    The 2nd version is too Golfic, but I am addicted to dropping curlies. – konijn Jan 21 '14 at 17:39
  • I like this answer. If I were to try to improve (which is not needed), I would say, 1. I would use powerSet, instead of set, or at least something with less overloaded meaning. 2. I would avoid 2nd nested loop as most of the inner loops are unused. I think memoization would be good for that (jsfiddle.net/ynotravid/kkwfnpu7/20). – Ynot Apr 10 at 23:30

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.

A much faster way to do Math.pow( 2, x ) if x is an integer is 1 << x.

A good name for the function might also be 'array_permutator'.

  • My main issue is this double-looping with the if-checking. – Incognito Dec 19 '11 at 20:33
  • Yes, I understand that. I cannot come up with an idea for eliminating the nested loop. So, wait and see if someone thinks of something. – Mike Nakis Dec 19 '11 at 20:39
  • Understood, thanks for all the help :). – Incognito Dec 19 '11 at 20:46

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.

I have two solutions for this, one being binary and one being recursive;

The binary would be as follows;

function getSubArrays(arr){
  var len = arr.length,
     subs = Array(Math.pow(2,len)).fill();
  return subs.map((_,i) => { var j = -1,
                                 k = i,
                               res = [];
                             while (++j < len ) {
                               k & 1 && res.push(arr[j]);
                               k = k >> 1;
                             }
                             return res;
                           }).slice(1);
}

console.log(JSON.stringify(getSubArrays(["a","b","c","d"])));

And the recursive one is as follows;

function getSubArrays(arr){
  if (arr.length === 1) return [arr];
  else {
  	subarr = getSubArrays(arr.slice(1));
  	return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
  }
}

console.log(JSON.stringify(getSubArrays(["a","b","c","d"])));

Try this simple one.

var input="abcde";
var len=input.length;
var str = "";
var p=Math.pow(2,len);
var twoPower;
for(i = 0; i < p; i++) 
{
    twoPower=p;
    for(j=0;j<len;j++)
    {
        twoPower=twoPower/2;
        str+= (i & twoPower ? input.charAt(j) : "");
    }
    str+="\n";
}
alert(str);

It's working method is so simple. What would you do if you have to find all binary numbers for a given a bit length? Yes the 8 4 2 1 method. if bit length is 3 then possible numbers are

4 2 1

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

These are the 8 possible values. The same method is used here but for 1's here is a character and for 0's nothing. So, number of possible combinations is (2^n)-1.

  • 2
    Welcome to CodeReview. As it is your code is little more than a code dump, please provide context towards why the OP should take your suggestion /what would differentiate it from what he's already doing. – Legato Apr 1 '15 at 17:21

In this collection of answers, I think we're missing the traditional recursive solution, which highlights the elegance of a recursive algorithm:

const subSeq = (s) => {
    if (s.length == 1) return ['', s] 

    // All the subSeq without the first char:
    const ss = subSeq(s.slice(1))

    // Return both those with and those without the first char
    return [...ss.map(ch => s[0] + ch), ...ss]
}

or more concisely stated, but perhaps harder to follow:

const subSeq = (s) => s.length == 1 
    ? ['', s] 
    : (ss=subSeq(s.slice(1)), 
       [...ss.map(ch => s[0] + ch), ...ss])

includes the empty string in the answer:

subSeq('abcd')
=> ["abc", "abcd", "ab", "abd", "ac", "acd", "a", "ad", "bc", "bcd", "b", "bd", "c", "cd", "", "d"]

protected by 200_success Apr 2 '16 at 1:25

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.