get all combinations for a string

Question

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.

Toscanini

Answer 1

This is what I ended up using.

var combinations = function (string)
{
    var result = [];

    var loop = function (start,depth,prefix)
    {
        for(var i=start; i<string.length; i++)
        {
            var next = prefix+string[i];
            if (depth > 0)
                loop(i+1,depth-1,next);
            else
                result.push(next);
        }
    }

    for(var i=0; i<string.length; i++)
    {
        loop(0,i,'');
    }

    return result;
}

Toscanini

But, I don't find your solution fitting the get all combinations intention. For instance, doing combinations('dog') gives [ 'd', 'o', 'g', 'do', 'dg', 'og', 'dog' ], which isn't all the combinations. god, go, gd are missing. A potential solution to that might be to split the result into two, reverse() the second half, then re-append to the original result to accommodate for the use case of a palindrome string. – Quag

As I said in the original question I didn't want permutations to be included. In my use case 'dog' and 'god' would get the same result and therefore be redundant. – Toscanini

Answer 2

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('')
}))

Ostraw

This give much more possible results than other functions, I think this should be the correct answer for most possible answers. – Bobby

the part where you say it is very easy to understand, that is a joke right? – Conscientious

Answer 3

You could use a nasty trick and increase a counter and use its binary representation as flags:

function combine(str){
   const result = [];
   for(let i = 1; i < Math.pow(2, str.length) - 1; i++)
      result.push([...str].filter((_, pos) => (i >> pos) & 1).join(""));
  return result;
}
console.log(combine('abcd'));

Jsbin

Maness

This is really fast, but is excluding combinations that are the same length as the original string. "ABC" should also have "CBA" as one of the results, for instance. Is there a modification to this that would include those combinations? – Feoffee

@sebastian you are looking for all possible permutations, not combinations – Maness

Answer 4

This is usiing loop as you expected easiest way.. good luck

        function mixString() {
            var inputy = document.getElementById("mixValue").value
            var result = document.getElementById("mix-result")
            result.innerHTML=""

            
            for (var i = 0 ; i < inputy.length; i++) {
               
                for (var b = 0 ; b < inputy.length; b++) {
                    
                    if (i == b) {
                        
                        result.innerHTML += inputy.charAt(i) + ","
                    }
                    else
                    {
                        result.innerHTML += inputy.charAt(i) + inputy.charAt(b) + ","
                    }
                    
                }

            }
        }

    <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
    
    <div class="container">
        <div class="panel panel-default">
            <div class="panel-heading">JavaScript string combination
</div>
            <div class="panel-body">
                <input id="mixValue" class="form-control" />
                <input type="button" onclick="mixString()" value="click" />
                <div id="mix-result"></div>
            </div>
        </div>
    </div>

Hortenciahortensa

Answer 5

function combinations(var1) {

    var temp;

    for (var i = 0; i < var1.length; i++) {
        var2 = "";

        temp = i;

        while (temp < var1.length) {

            var2 = var2.concat(var1.charAt(temp));
            // console.log(var2)
            if (i == var1.length - 1)
                document.getElementById('result').innerHTML += var2;

            else
                document.getElementById('result').innerHTML += var2 + ',';
            temp++;
        }
    }
}

Seasickness

Answer 6

You couldm take an iterative and recursive approach by using the character at the given key or not.

function combine(string) {
    function iter(i, temp) {
        if (i >= string.length) {
            result.push(temp);
            return;
        }
        iter(i + 1, temp + string[i]);
        iter(i + 1, temp);
    }

    var result = [];
    iter(0, '');
    return result;
}

console.log(combine('jump'));

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

Octodecimo

Answer 7

The accepted solution as of July 29, 2019 allows for duplicate strings to be returned in the array. The following adjustment fixes that little issue by adding a condition to the push.

            // however, we don't want duplicates so...
            if (!result.includes(next)) {
                result.push(next);    
            }

Jabon

Answer 8

Generators allow a very clean implementation:

// Very short generator produces all possible strings composed of the given chars!
let allStrings = function*(chars) {
  yield '';
  for (let prefix of allStrings(chars)) for (let c of chars) yield `${prefix}${c}`;
};

// Render the first 1000 strings
document.body.style.fontFamily = 'monospace';
let count = 0;
for (let str of allStrings('abcd')) {
  let div = document.createElement('div');
  div.innerHTML = `${(count + 1).toString().padStart(4, '0')}: ${str}`;
  document.body.appendChild(div);
  if (count++ > 1000) break;
}

Note that the very first result from allStrings is the empty string. If it's crucial to avoid this the following implementation can be used:

let allStrings = function*(chars, includeEmpty=false) {
  if (includeEmpty) yield '';
  for (let prefix of allStrings(chars, true)) for (let c of chars) yield `${prefix}${c}`;
};

Heretic

Answer 9

This is working solution please try this out:

let str = "abc"

function combination(data) {
    let result = []
    data = data.split("")
    for (let i = 0; i < data.length; i++) {
        let word = data[i];
        let newData = data.filter((el) => {
            return el !== data[i]
        })
        for (let j = 0; j < newData.length; j++) {
            if (j === newData.length - 1) {
                word = word + newData.join("");
                result.push(word);
            } else {
                for (let k = j + 1; k < newData.length; k++) {
                    let resultData = [...newData]
                    let temp = resultData[j];
                    resultData[j] = resultData[k];
                    resultData[k] = temp
                    let combineWord = word + (resultData.join(""));
                    result.push(combineWord)
                }
            }
        }
    }
    return result
}


console.log(combination(str))

Excision

Please read the question carefully: "I'm not asking for permutations, abc and acb shouldn't both be returned. Also the shortest being first in the array is important." Your answer does not address the question correctly. While other answers do include permutations, they do include shortest to longest combinations at least. – Pradeep

Answer 10

//all combinations of a string // dog => d,do,dog,og,g

function combinationString(){
    let str = 'dog';
    let combinationArray = [];

    for(i=0; i< str.length; i++){
        for(j=i+1; j<=str.length; j++){
            combinationArray.push(str.slice(i,j));
        }
    }
    console.log("Combination ", combinationArray);
}
combinationString()

Hairbreadth