title: Recursively generate ordered substrings from an ordered sequence of chars?
body: <p><strong><em>Edited after getting answers</em></strong><p>
  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.</p>
  
  <hr>
  
  <p>Say I have a string s of chars s[0]:s[N] and where each char s[i] &lt;= s[i+1]
  For example the string</p>
  
  <pre><code>aaacdddghzz
  </code></pre>
  
  <p>I want to generate all combinations of substrings while keeping the same relationship between chars.</p>
  
  <p>So for example I would get</p>
  
  <pre><code>a
  aa
  aaa
  ad
  aad
  aaad
  add
  aadd
  aaadd
  addd
  aaddd
  aaaddd
  d
  dd
  ddd
  .
  .
  .
  ac
  aac
  .
  .
  .
  acdddghzz
  aacdddghzz
  aaacdddghzz
  </code></pre>
  
  <p>But not</p>
  
  <pre><code>ca
  hdz
  ...etc
  </code></pre>
  
  <p>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</p>
  
  <p>For string aaacdddghzz</p>
  
  <pre><code>a=3
  d=3
  c=1
  g=1
  h=1
  z=2
  </code></pre>
  
  <p>and the formula is <code>(a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384</code>. There are 384 substrings that keep the s[i] &lt;=s [i+1] relationship.</p>
  
  <p>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.</p>