Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

get all combinations for a string

I'm trying to create a function in JavaScript that given a string will return an array of all possible combinations of the letters with each used at most once, starting with the shortest. e.g for the string ABC it would return:

A
B
C
AB
AC
ABC

I could use loops like so:

for(i=0; i<string.length; i++) {
   //add string[i]
}
for(i=0; i<string.length; i++) {
    for(a=i; a<string.length; a++) {
            //add string[i]+string[a]
    }
}
for(i=0; i<string.length; i++) {
    for(a=i; a<string.length; a++) {
        for(b=a; b<string.length; b++) {
            //add string[i]+string[a]+string[b]
        }
    }
}

But I don't know the length of the string, so wouldn't know how many loops to use.

Any ideas?

Edit: I'm not asking for permutations, abc and acb shouldn't both be returned. Also the shortest being first in the array is important.

This is not homework. It's for a program to solve a 'lights-out' type game.

like image 865
RedHatter Avatar asked Aug 21 '12 04:08

RedHatter


1 Answers

This is a recursive solution that I think is very easy to understand.

var tree = function(leafs) {
  var branches = [];
  if (leafs.length == 1) return leafs;
  for (var k in leafs) {
    var leaf = leafs[k];
    tree(leafs.join('').replace(leaf, '').split('')).concat("").map(function(subtree) {
      branches.push([leaf].concat(subtree));
    });
  }
  return branches;
};
console.log(tree("abc".split('')).map(function(str) {
  return str.join('')
}))
like image 97
matt3141 Avatar answered Oct 04 '22 04:10

matt3141