Print all possible strings that can be made by placing spaces

Question

I came across this problem.

Print all possible strings that can be made by placing spaces.

I also came across this solution.

var spacer = function (input) {
    var result = '' ;
    var inputArray = input.split('');
    var length = inputArray.length;
    var resultSize = Math.pow(2,length-1); // how this works
    for(var i = 0 ; i< resultSize ; i++){
        for(var j=0;j<length;j++){
            result += inputArray[j];
            if((i & (1<<j))>0){ // how this works
                result += ' ' ;
            }
        }
        result += '\n' ;
    }
    return result;
}

var main = function() {
    var input = 'abcd' ;
    var result = spacer(input);
    console.log(result);
}

main();

I am not getting how the marked lines work?

Can you clarify on what technique is being used? And what is the basic logic behind this? What are some of other areas where we can use this?

Thanks.

Answer 1

Let's take string abcd as an example. There are 3 possible places where space can be put:

1. Between "a" and "b"
2. Between "b" and "c"
3. Between "c" and "d"

So generally if length of your string is length then you have length - 1 places for spaces.

Assume that each such place is represented with a separate digit in a binary number. This digit is 0 when we don't put space there, and 1 when we do. E.g.:

a b c d

0 0 0 means that we don't put any spaces - abcd

0 0 1 means that we put space between "c" and "d" only - abc d

0 1 0 means that we put space between "b" and "c" only - ab cd

0 1 1 means ab c d

1 0 0 means a bcd

1 0 1 means a bc d

1 1 0 means a b cd

1 1 1 means a b c d

Converting 000, 001, 010, ..., 111 from binary to decimal will give us values 0, 1, 2, ..., 7.

With 3 places for spaces we have 8 options to put them. It's exactly 2^3 or 2^(length - 1).

Thus we need to iterate all numbers between 0 (inclusive) and 2^(length - 1) (exclusive).

Condition (i & (1 << j)) > 0 in the code you provided just checks whether digit at position j (starting from the end, 0-based) is 0 (and we don't need to insert space) or 1 (and space should be added).

Let's take value 6 (110 in binary) for example.

(6 & (1 << 0)) = 110 & 001 = 000 = 0 (condition > 0 is not met)

(6 & (1 << 1)) = 110 & 010 = 010 = 2 (condition > 0 is met)

(6 & (1 << 2)) = 110 & 100 = 100 = 4 (condition > 0 is met)

Answer 2

simple solution Using Javascript

 String.prototype.splice = function(idx, rem, str) {
    return this.slice(0, idx) + str + this.slice(idx + Math.abs(rem));
    };
    function printPattern(str, i, n){
    if(i==n){
    return;
    }
    var buff = str;
    var j = str.length - n + i;
    buff = str.splice(j,0," "); 
    console.log(buff);
    printPattern(str, i+1, n);
    printPattern(buff, i+1, n);
    }
    var str = "ABCD"
    printPattern(str, 1, str.length);
    console.log(str);

Answer 3

There are 2 possibilities between each 2 characters: either has space or not. If spaces are allowed only between characters then the number of possibilities for 4 characters is 2 * 2 * 2 or 2 ^ (length - 1)

Answer 4

resultSize = Math.pow(2, length - 1) says there are 2^n-1 possible ways to print a string given the problem definition. As far as to why that is the number of solutions is pretty easy to understand if you start with a string that has 2 characters and work your way upward. So pretend you have the string "ab". There is two solutions, you can put a space between a and b or you can not put a space between a and b. Lets add a character to get "abc". Well, we already know that there are two solutions for the string "ab" so we need multiply that solution by the number of ways you can put a space between b and c. Which is 2 so that gives us 2 * 2 solutions. You can extend that to a string of n size. So that means that the number of solutions is 2 * 2 * 2 * 2 * ... n - 1. Or in otherwords 2 ^ n-1.

The next part is a little trickier, but its a clever way of determining how many spaces and where they go in any given solution. The bitwise & takes the each bit of two numbers, compares them, then spits out a new number where each bit is a 1 if both the bits of the two numbers were 1, or 0 if the bits were not 1 and 1. For example (binary numbers):

01 & 01 = 01
10 & 01 = 00

Or a bigger example:

10010010 & 10100010 = 10000010

The << operator just moves all bits n position to left where n is the right hand expression (multiply by 2 n times). For example:

1 << 1 = 2
2 << 1 = 4
2 << 2 = 8
1 << 4 = 8

So back to your code now. Lets break down the if statement

if(i & (1 << j) > 0){ ... }

In english this says, if the number index of the solution we are looking at shares any 1 bits with 1 shifted by the index of the character we are looking at, then put a space after that character. Olexiy Sadovnikov's answer has some good examples of what this would look like for some of the iterations.

Its also worth noting that this is not the only way to do this. You could pretty easily determine that the max number of spaces is n - 1 then just linearly find all of the solutions that have 0 spaces in them, then find all the solutions that have 1 space in them, then 2 spaces .... to n - 1 spaces. Though the solution you posted would be faster than doing it this way. Of course when your talking about algorithms of exponential complexity it ultimately won't matter because strings bigger than about 60 chars will take longer than you probably care to wait for even with a strictly 2^n algorithm.

In answer to the question of how these techniques can be used in other places. Bit shifting is used very frequently in encryption algorithms as well as the bitwise & and | operators.

Answer 5

'''
The idea was to fix each character from the beginning and print space separated rest of the string.
Like for "ABCD": 
A BCD # Fix A and print rest string
AB CD # Add B to previous value A and print rest of the string
ABC D # Add C to previous value AB and print rest of the string
Similarly we can add a space to produce all permutations.
Like:
In second step above we got "AB CD" by having "A" as prefix
So now we can get "A B CD" by having "A " as a prefix
'''

def printPermute(arr, s, app):
if len(arr) <= 1:
    return 
else:
    print(app +''+arr[0:s] +' '+ arr[s:len(arr)])
    prefix = app + ''+arr[0:s]
    suffix = arr[s:len(arr)]
    printPermute(suffix, 1, prefix)
    printPermute(suffix, 1, prefix+' ') #Appending space

printPermute("ABCDE", 1, '') #Empty string

Answer 6

• .pow is a method from Math which stands for "power". It takes two arguments: the base (here 2) and the exponent. Read here for more information.

• & is the bitwise AND operator, it takes the two binary representation of the numbers and performs a logical AND, here's a thread on bitwise operators

---

EDIT: why Math.pow(2,length-1) gives us the number of possible strings?

I remember doing it in an exercise last year in math class, but I'll try to explain it without sums.

Essentially we want to determine the number of strings you can make by adding one or no space in between letters. Your initial string has n letters. Here's the reason why:

Starting from the left or the word after each letter you have two choices

1 - to put a space

2 - not to put a space

You will have to choose between the two options exactly n-1 times.

This means you will have a total of 2^(n-1) possible solutions.