Edited after getting answers
Some excellent answers here. I like Josh's because it is so clever and uses C++. However I decided to accept Dave's answer because of it's simplicity and recursion. I tested them both and they both produced identical correct results (although in a different order). So thanks again everyone.
Say I have a string s of chars s[0]:s[N] and where each char s[i] <= s[i+1] For example the string
aaacdddghzz
I want to generate all combinations of substrings while keeping the same relationship between chars.
So for example I would get
a
aa
aaa
ad
aad
aaad
add
aadd
aaadd
addd
aaddd
aaaddd
d
dd
ddd
.
.
.
ac
aac
.
.
.
acdddghzz
aacdddghzz
aaacdddghzz
But not
ca
hdz
...etc
Now I know how to work out how many combinations there are. You create a histogram of the frequency of letters in the string. So in the above example the that would be
For string aaacdddghzz
a=3
d=3
c=1
g=1
h=1
z=2
and the formula is (a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384. There are 384 substrings that keep the s[i] <=s [i+1] relationship.
So the question is how do I generate those 384 substrings recursively? Actually an iterative method would be just as good, maybe better as large strings with many unique chars might cause the stack to overflow. This sounds like homework but it isn't. I'm just useless at coming up with algorithms like this. I use C++ but pseudocode would be fine.