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?

Schild

Since we want all combinations, with charAt(i) and without it, we need to separate the two situations. Those combinations without charAt(i) is taken care of in the next iteration of the for-loop, by the magic of deleteCharAt() before the end of the current iteration. – Lindquist

Answer 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

Spirketing

Answer 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.

Mandamus

Thanks! This makes understanding the solution easier. – Emancipate

Brilliant! I believe this is the most intuitive to implement – Horseshit

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

@Vikash, BA is AB and CA is AC and CBA is ABC because combination not permutation. – Broderickbrodeur

Answer 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).

Actinozoan

Answer 4

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.

Caprice

Answer 5

Below code is to generate permutation and combination of string, basically the concept is to pick one character at a time:

public class permutecombo
{
  static void initiate(String s)
  {
    permute("", s);
    System.out.println("----------------------------------------- ");
    combo("", s);
    System.out.println("----------------------------------------- ");
  }

  static void combo(String prefix, String s)
  {
    int N = s.length();

    System.out.println(prefix);

    for (int i = 0 ; i < N ; i++)
      combo(prefix + s.charAt(i), s.substring(i+1));
  }
  static void permute(String prefix, String s)
  {
    int N = s.length();

    if (N == 0)
      System.out.println(" " + prefix);

    for (int i = 0 ; i < N ; i++)
      permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
  }

  public static void main(String[] args)
  {
    String s = "1234";
    initiate(s);
  }
}

Ammeter

Answer 6

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.

Ceresin

Answer 7

Here is C++ code without the tricky backtracking step in OP's question.

#include <iostream>
#include <string>
using namespace std;
static const string in("abc");
void combine(int i, string out) // each out is a combo of letters up to ith
{
    if (i==in.size()) { // all letters have been looked at
        cout << out << endl;
        return;
    }
    combine(i+1, out);  // showing the ith letter in final out
    combine(i+1, out+in[i]); // skipping the ith letter in final out
}

int main()
{
    combine(0, "");
    return 0;
}

I hope this better captures the spirit of combinations.

Lindquist

Would you add explanation? – Broderickbrodeur

@Cloud-Cho do you think that the added comments make sense? – Lindquist

Thanks for the comment. It helps. I ran your code and it printed out from the last letter, which is 'c'. That is interesting. Would you share how you came out with algorithm (or reference)? – Broderickbrodeur

I don't remember the exact source of this idea. It may or may not come from one of those interview prep books. Thank you for actually compiling the code and checking results! – Lindquist

Answer 8

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

means that you have

n^(n-1)/2 pairs of combinations.

The iterative for-loop doesn't stop after the recursive function call so you need to delete the last char in the output buffer because you don't want to get

n^n/2 pairs of combinations.

In a graph theory it would be a short circuit.

Directory

Answer 9

// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

import java.util.*;
public class Permutation {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("ENTER A STRING");
        Set<String> se=find(in.nextLine());
        System.out.println((se));
    }
    public static Set<String> find(String s)
    {
        Set<String> ss=new HashSet<String>();
        if(s==null)
        {
            return null;
        }
        if(s.length()==0)
        {
            ss.add("");
        }
        else
        {
            char c=s.charAt(0);
            String st=s.substring(1);
            Set<String> qq=find(st);
            for(String str:qq)
            {
                for(int i=0;i<=str.length();i++)
                {
                    ss.add(comb(str,c,i));
                }
            }
        }
        return ss;

    }
    public static String comb(String s,char c,int i)
    {
        String start=s.substring(0,i);
        String end=s.substring(i);
        return start+c+end;
    }

}


// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

Complication

Answer 10

import com.google.common.collect.Lists;

import java.util.List;

public class Combinations {
    public static String[] getCombinations(final String input) {
        final List<String> combinations = Lists.newArrayList();
        getCombinations(input.toCharArray(), combinations, 0, "");
        return combinations.toArray(new String[0]);
    }

    private static void getCombinations(final char[] input, final List<String> combinations, final int index, final String combination) {
        if (index == input.length) {
            combinations.add(combination);
            return;
        }
        getCombinations(input, combinations, index + 1, combination + String.valueOf(input[index]));
        getCombinations(input, combinations, index + 1, combination);
    }

}

Corresponding tests:

import org.hamcrest.Matchers;
import org.junit.Test;

import static org.hamcrest.MatcherAssert.assertThat;

public class CombinationsTest {
    @Test
    public void testCombinations() {
        verify(Combinations.getCombinations(""), "");
        verify(Combinations.getCombinations("a"), "a", "");
        verify(Combinations.getCombinations("ab"), "ab", "a", "b", "");
        verify(Combinations.getCombinations("abc"), "abc", "ab", "ac", "a", "bc", "b", "c", "");
        verify(Combinations.getCombinations("abcd"),
                "abcd", "abc", "abd", "ab", "acd", "ac", "ad", "a", "bcd", "bc", "bd", "b", "cd", "c", "d", "");
    }

    private void verify(final String[] actual, final String... expected) {
        assertThat(actual, Matchers.equalTo(expected));
    }
}

Selassie

Answer 11

I think that the line outstr.deleteCharAt(outstr.length() - 1) is backtracking method.

Here is a good example from the chapter 7 at John Mongan's book:

Given string at the example: wxyz
   Now John showed how he came out with all combinations from the string:
   (please, keep in mind when you reached at the end of the string you need to return. This is letter 'z' in this example.)

   ---->
   w wx wxy wxyz
   wxz <- wxyz - wxy - wx: z and y are removed (1)
   wy <- wxz - wx - w: z and x are removed (2) wyz
   wz <- wyz - wy - w: z and y are removed (3)

   x <- wz - w - ' ': z and w are removed (4) xy xyz
   xz <- wyz - xy - x: z and y are removed (5)

   y <- xz - x - ' ': z and x are removed (6) yz

   z < yz - y - ' ': z and y are removed (7)

The steps (1) ~ (7) are backtracking and could be implemented by outstr.deleteCharAt(outstr.length() - 1).

---

As reference for better understanding,
here is John's pseudo code directly from the book:

For each letter from input start position to end of input string
   Select the letter into the current position in output sting
   Print letters in output string
   If the current letter isn't the last in the input string
Generate remaining combination staring at next position with iterations starting at next letter beyond the letter just selected

The last line starting with 'Generate' is the backtracking.

Broderickbrodeur