All combinations of inserting spaces into String

[vladul11]

Hey guys!
If i have for example the string "abcde" and i want to return all the String possibiliets resulted in inserting k spaces ( " " ), what would be a correct approach? Ex:
k=0
abcde
k=1
a bcde
ab cde
abc de
abcd e
k=2
a b cde
a bc de
a bcd e
ab c de
.....
k = length("abcde")-1
a b c d e

Thank you!

[nuzzle]

what would be a correct approach?

It's a combinatorial problem.

With a string length of N there will be N-1 positions where a space is either insert or not inserted. Each such combination can be represented by a binary number. There will be 2^(N-1) numbers. When N = 5 for example you have 2^(5-1) = 16, like

0000
0001
0010
0011
0100
....
1110
1111

where a 1 means there's a space in that position and a 0 means there's not. So the number of spaces (k) simply is the number of 1's in the binary number.

So one solution approach is to loop through all integers between 0 and 2^(N-1) - 1 and for each integer generate the string corresponding to the bit pattern of that integer. This will give all possible string/space combinations. The strings can then be arranged in order of increasing number of spaces by sorting them on length.

[henryswanson]

Also, if you want exactly k spaces, not k-or-fewer, you could use a recursive method. I know nothing about its efficiency though. It would go something like this:

public static void main(String[] args) {
		System.out.println(foo("abcde", 3));
	}
	
	public static List<String> foo(String s, int numSpaces) {
		List<String> list = new ArrayList<String>();
		if(s.length() <= numSpaces) return list;
		int[] indices = new int[numSpaces];
		for(int i = 0; i < numSpaces; i++)
			indices[i] = i + 1;
		while(bar(indices, numSpaces - 1, s.length())) {
			//insert spaces somehow, one for each entry of indices
		}
		return list;
	}
	
	public static boolean bar(int[] indices, int indexToMove, int whenToStop) {
		if(++indices[indexToMove] == whenToStop) {
			if(index == 0) return false;
			if(!bar(indices, indexToMove - 1, whenToStop - 1)) return false; //if the call beneath it is false, pass that upwards
			indices[indexToMove] = indices[indexToMove - 1] + 1; //moves this index to right after the previous one
		}
		return true;
	}

[nuzzle]

Also, if you want exactly k spaces, not k-or-fewer, you could use a recursive method. I know nothing about its efficiency though. It would go something like this:

The problem you describe is a standard combinatorial problem called "finding all k-element subsets of an n-element set". The n elements would be the positions in the string where a space can be inserted and k would be the actual number of spaces that's inserted.

Here's another solution to the problem. It uses a successor approach, that is from one initial k-subset all other k-subsets are generated in sequence,

http://compprog.wordpress.com/2007/1...ombinations-1/

Since the OP wanted all k-subsets the easiest approach is the one I suggested. All possible subsets are first generated and then sorted according to k number.

But it's also possible to generate all k-sets one after the other, from k=0 and onwards up to k=n. Then no sorting is necessary.

I don't know the complexity of k-subset generation but a sort is O(N*logN) so that will be the overall complexity of my suggestion.