Algorithm to generate all combinations of a string

Question

I found a link online that shows an algorithm to generate all combinations of a string: http://www.mytechinterviews.com/combinations-of-a-string

Algorithm is copied below.

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

What I don't understand is the line:

outstr.deleteCharAt(outstr.length() - 1);

If I remove this line, the program obviously does not work anymore, but why is this needed in the first place? I understand the recursive idea where we vary an initial character and recurse on the remaining characters, but the deleteChar line does not seem to fit in logically anywhere. What was the reason for adding the outstr.deleteCharAt line?

Solution 1

The call of outstr.deleteCharAt counters the effect of outstr.append by deleting the last character of the outstr.

Each loop iteration proceeds as follows:

1. append a character
2. print the result
3. perform a recursive invocation at the level i+1
4. remove the character we added at step 1

Solution 2

Simplest way of calculating the possible combinations of strings is here ...

Mathematically to find R combinations in a given lot of N = NcR

So what we are finding here is, all possible combinations = Nc0 + Nc1 .... + Ncn = 2 Pow N

So you get 2 Pow N combinations for given word of length N characters.

If you represent 1 to (2 Pow N) integers in binary, and place your char in the place where 1 is present, finally you would get the solution.

Example:

Input : ABC

Solution :

ABC length is 3. So possible combinations 2 Pow 3 = 8

If 0 - 8 represented in binary

000 =

001 = C

010 = B

011 = BC

100 = A

101 = AC

110 = AB

111 = ABC

all possible combinations are shown above.

Solution 3

It balances the first line of the loop body, restoring outstr to what it was at the top of the loop body (by removing the character from instr that was appended).

Solution 4

We can generate all the sub strings of a string by using the bit concept which has been mentioned previously. Here is the code (in C++ , but you get the idea) to do that : -

string s;
int n = s.size();
int num = 1<<n;
for(int i =1; i< num ; i++){ //Checks all the permutations.
    int value = i;
    int j, pos;
    for (j=1, pos=1; j < num; j<<=1, pos++) //Finds the bits that are set
        if (i & j)
            cout<<s[pos-1]; //You can print s[n-pos] to print according to bit position
    cout<<endl;        
}

Eg;- String s = abc ,

 The size is 3  . So we check from 1 to 7 ( 1<<3).
 for i = 1 ( 001 ) , the first bit is set, so a is printed.
 for i = 2 ( 010 ) , the second bit is set, so b is printed.
 for i = 3 ( 011 ) , the first and second bit are set, so ab is printed.
 .
 .
 .
 for i = 7 ( 111 ) , all three bits are set, so abc is printed.

Solution 5

It fits very logically. You see what we have here is a recursive algorithm. At each step in position i we put a letter of the string then call the function recursively to put another letter on the next position. However, when we return from recursion, we need to remove the character we put initially, so that we can replace it with the next possible one in the sequence. Example:

append a on pos 0 -> a
call recursion
append a on pos 1 -> aa
call recursion
append a on pos 2 -> aaa
return from recursion
remove a from pos 2 -> aa
append b on pos 2 -> aab
return from recursion
remove b from pos 2 -> aa
append c on pos 2 -> aac
etc.

View more solutions

Comments

[asgs]

Thanks! This makes understanding the solution easier.

[Vikrant Goel]

Brilliant! I believe this is the most intuitive to implement

[Vikash]

It doesn't have BA, CA, CBA .. and others, I guess those are possible and different strings.