8

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 anywhere 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.

svenstaro
  • 1,783
  • 2
  • 21
  • 31
  • 3
    http://www.cplusplus.com/reference/algorithm/next_permutation/? – Anycorn Jun 11 '10 at 21:14
  • 1
    is your question really about how to implement cartesian product in C++? how general do you want to be with repetition and number of characters? – Anycorn Jun 11 '10 at 21:31
  • 1
    I don't want permutation, I want variations with repetitions. I've looked at the cartesian product but it looks like a lot more than what I want to do, at least based on the sample implementations I've found so far. – svenstaro Jun 11 '10 at 21:47
  • you can use permutations, for example generate set of ordered tuples(4 in your example), permute each tuple to obtain all possible permutations. order is not quite like you want, but you can fix it – Anycorn Jun 11 '10 at 21:55
  • There's nothing wrong with the recursive solution. The stack there grows linearly while the running time grows exponentially, so you run out of patience long before you run out of stack. –  Jun 11 '10 at 22:10

3 Answers3

6

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_lengthalphabet_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
aioobe
  • 413,195
  • 112
  • 811
  • 826
  • 1
    I have a question what exactly is :**String str = Integer.toString(i, alphabet.length);** I am trying to implement it in C++ by simply doing string std = std::to_string(i) what is the difference? – Hani Goc Feb 14 '14 at 10:51
  • 1
    @HaniGoc to_string converts only to base 10, while toString converts to the given base (alphabet.length) – Mohamed El-Nakeep Feb 13 '15 at 18:51
1

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.

Anycorn
  • 50,217
  • 42
  • 167
  • 261
0

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;
 }
DejanM
  • 81
  • 1
  • 4
  • 3
    Welcome to Stack Overflow! While you may have solved this user's problem, code-only answers are not very helpful to users who come to this question in the future. Please edit your answer to explain why your code solves the original problem. – Joe C Feb 25 '17 at 12:18