How to generate all variations with repetitions of a string?

Question

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.

Answer 1

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

Answer 2

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.