Find all the combinations of a string Javascript

Question

I want to find all the combinations of a string in javascript. I looked up previously asked questions but there is one output missing and I don't know how to find it.

My code is:

    <html>
    <head></head>
    <body>
    <label>Enter word/sentence to generate combinations:</label>
        <input type="text" name="comb"/></br>
        <input type="button" value="Get Combination" name="combbtn" onclick="substrings()"/>
        <script>
            function substrings(){
                var str=document.getElementsByTagName("input")[0].value;
                var i, j, result = [];
                  for (i = 0; i < str.length; i++) {
                      for (j = i + 1; j < str.length + 1; j++) {
                          result.push(str.slice(i, j));
                      }
                  }
                  alert(result);
            }
        </script>
    </body>
</html>

When I try "dad" as input, the expected output is:-

d,a,da,d,dd,ad,dad

But my code somehow misses

"dd"

How can I include it. Any help/suggestion?

The question I'm facing is phrased like that. Sorry If it's misleading. All i want is to include "dd" to my output. — diksha msc, Aug 16 '17 at 20:11
@dikshamsc If that is the expected output then the question is wrong. — Andrew Morton, Aug 16 '17 at 20:13
@dikshamsc Please define "substring" as used in the question - perhaps you have been given a different definition than the conventional one. — Andrew Morton, Aug 16 '17 at 20:16
Your output has "d" twice but not "da" and "ad" and "dd" twice. — James, Aug 16 '17 at 20:29

marvel308 · Accepted Answer · 2017-08-16T20:40:35.307

what you need to do is print all subsequences, this code would do that

function printSubsequences(str){
    let len = str.length, result = [];
    for(let i=1; i<(1<<len); i++){
        let temp = "";
        for(let j=0; j<len; j++){
            if((i&(1<<j))){
                temp = temp +str.charAt(j);
            }
        }
        result.push(temp);
    }
    console.log(result);
}
printSubsequences('dad');

Note the time complexity is exponential

consider a n digit number, the loop

for(let i=1; i<(1<<len); i++)

covers all numbers from 1 to 2^(n-1). Since all possible combinations can be represented in this number i, we need to check for a given i which bits were set

for(let j=0; j<len; j++)

travels through all possible bits and checks if (i & 2^(j-1)) is set or not, if it is set then that character is a part of the current string. here is the strings represented in 3 bits

"d" 001
"a" 010
"da" 011
"d" 100
"dd" 101
"ad" 110
"dad" 111

Also could you please explain the logic on for loops and if condition. I get really confused with bitwise shift operators. — diksha msc, Aug 16 '17 at 20:32
0'th bit represents "d", 1'th represents "a" and 2nd represents "d" — marvel308, Aug 16 '17 at 20:41

ProfDFrancis · Answer 2 · 2017-08-16T20:42:52.630

0

For n characters, you want 2^n-1 possibilities

So let's use binary for it:

For n characters, let a variable run from 0 to 2^n-1. Examine the binary digits of the variable. There will be n of them.

When a digit is 0, omit the character; when a digit is 1, show the corresponding character.

Obviously you don't want the empty output, and that is why you are not starting your loop variable at 0.

    let str="dad";
    let n=str.length;
    for (i=1;i<2**n-1;i++) {
      let out="";
      for (c=0;c<n;c++){
        if (i & (2**c) ) {
          out += str[c];
        }
      }
    console.log(out);
    }

d a da d dd ad

edited Aug 16 '17 at 20:42

answered Aug 16 '17 at 20:12

ProfDFrancis

8,816
1
17
26

Well yeah.. But all i want is to include repeating subelement like dd in dad. But i don't know how to do that. – diksha msc Aug 16 '17 at 20:15

Find all the combinations of a string Javascript

2 Answers2

For n characters, you want 2^n-1 possibilities

Linked