Dynamic Nested For Loops

[GenTiradentes]

I'm working on a project right now where I'm wanting to generate every possible string up to N characters in length. (It's for a useful purpose, not just some random whim. And no, it's not homework of any sort.)

So the way I've decided to do this is by creating a series of nested for loops, one for every character of the string. The problem is that I would have to create the same number of for loops as there are characters in the string, but I want the number of characters to be dynamic.

I strongly doubt that C++ allows any sort of run-time code generation that would make something like this easy, so I'm kind of at a stalemate. Can anyone give me some ideas on how to do this?

Thanks, I appreciate the help.

[jsmith]

string s;
for( size_t s_len = 1; s_len <= N; ++s_len ) {
   s += '\0';
   for( char each_char = 'A'; each_char <= 'Z'; ++each_char ) {
       s[ s.length() - 1 ] = each_char;
       cout << s << endl;
   }
}

for example

(uncompiled, untested)

[tition]

There are certainly many ways to do it. Here is my way to do it. The idea is simple: How do we count?
1,2,3,...,9,
When we reach 9, we flip the last digit to zero and insert the smallest possible digit in front.

That is precisely what the function Increment() in the below code does: it increments the last char if it can. If it can't, Increment() "flips" the last char back and proceeds to the second to last digit, and so on.

The advantage of my approach is that it could save the careless user from calling a too large combinatorial problem.

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>

class MyString: public std::string
{
public:
void Increment();
};
char MinChar='A';
char MaxChar='Z';
void MyString::Increment() 
{ if (this->size()==0){this->push_back(MinChar); return;}
   for (int i=this->size()-1;i>=0;i--)
  { if ((*this)[i]<MaxChar)
    { (*this)[i]++;
      return;
    }
    else
    { (*this)[i]=MinChar;
    }
  } 
  this->push_back(MinChar);
  (*this)[0]=MinChar;
  return;
}

int _tmain(int argc, _TCHAR* argv[])
{ MyString s;
  std::string tempS;
  for (int i=0;i<26*26+26;i++)
  { s.Increment();
    std::cout<<s<<" ";
  }
  int x;
  std::cin>> x;
  return 0;
}

[GenTiradentes]

Sweet implementation, Tition. Thanks both of you for the input, I'll have to try this out.

[jsmith]

Sorry, mine had a bug. This one I actually tested:

#include <boost/static_assert.hpp>
#include <iostream>
#include <string>

using namespace std;

template< char First, char Last, size_t N >
struct Generator {
   BOOST_STATIC_ASSERT( First <= Last );

   Generator() : s( 1, First ) {}

   string operator()() {
       string ret_val = s;

       if( s[ s.length() - 1 ] < Last ) {
           ++s[ s.length() - 1 ];
           return ret_val;
       }

       if( s == string( s.length(), Last ) ) {
           s = s.length() == N ? string() : string( s.length() + 1, First );
           return ret_val;
       }

       for( string::size_type i = s.length(); i; --i )
           if( s[ i - 1 ] == Last )
               s[ i - 1 ] = First;
           else {
               ++s[ i - 1 ];
               break;
           }

       return ret_val;
   }
   string s;
};

int main() {
    Generator<'A', 'Z', 3> g;
    string s( g() );
    while( !s.empty() ) {
        cout << s << endl;
        s = g();
    }
}

[tition]

Just a note on the number of strings:
If you have N letters to choose from, and your strings are of length k, then you have N^k different strings. If you look at all strings of length k or less, then their number is of course

1+N+N^2+...+N^k = (N^(k+1)-1)/(N-1)

if we count the empty string and one less otherwise:

(N^(k+1)-1)/(N-1) -1

These numbers can get very big very quickly!

[GenTiradentes]

I am aware of this. Dealing with this many strings proposes an interesting logistics problem, but I'll get it sorted out.

Thanks for the help.