How to find all the different combinations as units of different lengths of the characters of a string

Question

Hi I want to find all the different combinations rather linear selections of characters from a given string without losing sequence as units of different sizes. Example:

Lets say a word "HAVING"

Then it can have combinations like (spaces separating individual units).

HA VI N G
HAV ING
H AV I N G
HAVIN G
H AVING
H AVIN G
HA VING
H AVI NG

....

Like this all the different selections of units of different lengths.

Can someone give a prototype code or algo idea.

Thanks, Kalyana

Since you've asked for it in c#, java or c++, let me give you a simple generic algorithm: `String target = "H A V ING"; if (target.removeAllSpacesEverywhereInTheString() == "HAVING") { // This is the one !} else { // Nope }` Of course you will have to implement removeAllSpacesEverywhereInTheString or find library functions that do things like that in the specific language of your choice. — arunkumar, Aug 09 '11 at 11:51
@Jim the answers below seem much more complex than our String.Replace && compare don't you think ? — arunkumar, Aug 09 '11 at 16:29

score 4 · Answer 1 · answered Aug 09 '11 at 11:51

4

In a string of size n, you have n-1 positions where you could place spaces (= between each pair of consecutive letters). Thus, you have 2^(n-1) options, each represented by a binary number with n-1 digits, e.g., your first example would be 01011.

That should give you enough information to get started (no full solution; this sounds like homework).

answered Aug 09 '11 at 11:51

Heinzi

167,459
57
363
519

Thanks for the solution. Actually its not homework, and after this it gets complicated. Now I need if I have different permutations of the word. And I need the counts of each individual count produced and it needs to run in a distributed system. Thats the actual problem I am facing. I am sorry I forgot to mention about the distributed algo requirement. – user716843 Aug 09 '11 at 16:31
@user716843: So, where exactly are you stuck? (Maybe it might be worth starting a new question where you also detail your distributed requirements?) – Heinzi Aug 09 '11 at 18:59
I can get the individual combinations. But in a map reduce design, the processor breaks the whole thing down into subsets and the count of individual possible units when a file has a lot of individual strings to which this is applied. The problem is when I program in native Hadoop it can be done, but for efficiency and other substring computations when I use java code, the reduce step fails. The actual problem is to count the combinations of words in a string. For simplicity I made it characters in a word. I will however start a new question. BTW, thanks a lot :) – user716843 Aug 10 '11 at 04:08

score 1 · Answer 2 · answered Aug 09 '11 at 11:52

Simple recursive solution. Two sets are the first letter and the rest of the word. Find all combinations on the rest of the word. Then put the second letter with the first, and find all combinations on the rest of the word. Repeat until the rest of the word is 1 letter.

score 0 · Answer 3 · answered Aug 09 '11 at 11:52

It's just a power set isn't it? For every position between two letters in your string you do or do not have a space. So for a string of length 6 there are 2 to the power of 5 possibilities.

A simple recursive function will enumerate all the possibilities. Do you need help writing such a function or were you just looking for the algorithm?

score 0 · Answer 4 · answered Aug 09 '11 at 11:53

Between each letter, there's either a separator or there isn't. So recursively go through the word, trying out all combinations of separators/no-separators.

function f( word )
    set = word[0] + f( substring(word, 1) )
    set += word[0] + " " + f( substring(word, 1) )
    return set;

score 0 · Answer 5 · answered Aug 09 '11 at 11:59

0

My solution
Make it something like

void func(string s)
{  
  int len=s.length();
  if(len==0)
  return;
  for(int i=1;i<=len;i++)
  {
    for(int j=0;j<i;j++)
    cout<<s[j];
    cout<<" ";
    func(s[i]);
  }
  return;
}

answered Aug 09 '11 at 11:59

Shadow

6,161
3
20
14

score 0 · Answer 6 · answered Aug 09 '11 at 12:22

Recursion. In java:

public static List<List<String>> split (String str) {
    List<List<String>> res = new ArrayList<List<String>>();
    if (str == null) {
        return res;
    }
    for (int i = 0; i < str.length() - 1; i++) {
        for (List<String> list : split(str.substring(i + 1))) {
            List<String> tmpList = new ArrayList<String>();
            tmpList.add(str.substring(0, i + 1));
            for (String s : list) {
                tmpList.add(s);
            }
            res.add(tmpList);
        }
    }
    List<String> tmpList = new ArrayList<String>();
    tmpList.add(str);
    res.add(tmpList);
    return res;
}

public static void main(String[] args) {
    for (List<String> intermed : split("HAVING")) {
        for (String str : intermed) {
            System.out.print(str);
            System.out.print(" ");
        }
        System.out.println();
    }
}

How to find all the different combinations as units of different lengths of the characters of a string

6 Answers6