How to generate all variations with repetitions of a string?

I want to generate all variations with repetitions of a string in C++ and I'd highly prefer a non-recursive algorithm. I've come up with a recursive algorithm in the past but due to the complexity (r^n) I'd like to see an iterative approach.

I'm quite surprised that I wasn't able to find a solution to this problem anywh开发者_如何学JAVAere on the web or on StackOverflow.

I've come up with a Python script that does what I want as well:

import itertools

variations = itertools.product('ab', repeat=4)
for variations in variations:
        variation_string = ""
        for letter in variations:
                variation_string += letter
        print variation_string

Output:

aaaa aaab aaba aabb abaa abab abba abbb baaa baab baba babb bbaa bbab bbba bbbb

Ideally I'd like a C++ program that can produce the exact output, taking the exact same parameters.

This is for learning purposes, it isn't homework. I wish my homework was like that.

You could think of it as counting, in a radix equal to the number of characters in the alphabet (taking special care of multiple equal characters in the alphabet if that's a possible input). The aaaa aaab aaba ... example for instance, is actually the binary representation of the numbers 0-15.

Just do a search on radix transformations, implement a mapping from each "digit" to corresponding character, and then simply do a for loop from 0 to word_length^{alphabet_size}

Such algorithm should run in time linearly proportional to the number of strings that needs to be produced using constant amount of memory.

Demonstration in Java

public class Test {
    public static void main(String... args) {

        // Limit imposed by Integer.toString(int i, int radix) which is used
        // for the purpose of this demo.
        final String chars = "0123456789abcdefghijklmnopqrstuvwxyz";

        int wordLength = 3;
        char[] alphabet = { 'a', 'b', 'c' };

        for (int i = 0; i < Math.pow(wordLength, alphabet.length); i++) {

            String str = Integer.toString(i, alphabet.length);

            String result = "";
            while (result.length() + str.length() < wordLength)
                result += alphabet[0];

            for (char c : str.toCharArray())
                result += alphabet[chars.indexOf(c)];

            System.out.println(result);
        }
    }
}

output:

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

here is general recipe, not C++ specific to implement product:

Take product input string "abc.." to generate matrix "abc.."x"abc..". N^2 complexity. represent matrix as vector and repeat multiplication by "abc", complexity (N^2)*N, repeat.

STL like function for next_variation. Accept iterators of any container of number like type. You can use float/doubles also. Algorithm it self is very simple. Requirement for iterator is to be only forward. Even a std::list<...> can be used.

template<class _Tnumber, class _Titerator >
 bool next_variation
  (
       _Titerator const& _First
     , _Titerator const& _Last
     , _Tnumber const& _Upper
     , _Tnumber const& _Start = 0
     , _Tnumber const& _Step  = 1
  )
  {
   _Titerator _Next = _First;
   while( _Next  != _Last )
    {
      *_Next += _Step;
     if( *_Next < _Upper )
      {
       return true;
      }
     (*_Next) = _Start;
     ++_Next;
    }
   return false;
  }

int main( int argc, char *argv[] )
 {
  std::string s("aaaa");
  do{
      std::cout << s << std::endl;
  }while (next_variation(s.begin(), s.end(), 'c', 'a'));

  std::vector< double > dd(3,1);
  do{
   std::cout << dd[0] << "," << dd[1] << "," << dd[2] << ","  << std::endl;
  }while( next_variation<double>( dd.begin(), dd.end(), 5, 1, 0.5 ) );

  return EXIT_SUCCESS;
 }