c++ - 如何通过重复字符串生成所有变体？

Question

我想用 C++ 中的字符串重复生成所有变体，我非常喜欢非递归算法。过去我想出了一个递归算法，但由于复杂性 (r^n)，我希望看到一种迭代方法。

令我感到非常惊讶的是，我无法在网络或 StackOverflow 上的任何地方找到解决此问题的方法。

我想出了一个 Python 脚本，它也可以执行我想要的操作:

import itertools

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

输出:

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

理想情况下，我想要一个 C++ 程序，它可以产生准确的输出，采用完全相同的参数。

这是出于学习目的，不是家庭作业。我希望我的家庭作业是那样的。

Answer 1

您可以将其视为计数，基数等于字母表中的字符数(如果可能输入，请特别注意字母表中的多个相等字符)。例如，aaaa aaab aaba ... 示例实际上是数字 0-15 的二进制表示。

只需搜索基数转换，实现从每个“数字”到相应字符的映射，然后简单地执行从 0 到 word_length^{alphabet_size}

的 for 循环

此类算法的运行时间应与需要使用恒定内存量生成的字符串数量成线性比例。

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);
        }
    }
}

输出:

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