-
March 28th, 2011, 02:20 PM
#1
All combinations of inserting spaces into String
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!
-
March 28th, 2011, 07:26 PM
#2
Re: All combinations of inserting spaces into String
Originally Posted by vladul11
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.
Last edited by nuzzle; March 30th, 2011 at 12:05 AM.
-
March 31st, 2011, 08:26 PM
#3
Re: All combinations of inserting spaces into String
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:
Code:
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;
}
-
April 1st, 2011, 12:03 AM
#4
Re: All combinations of inserting spaces into String
Originally Posted by 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:
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.
Last edited by nuzzle; April 1st, 2011 at 06:35 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|