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

我想用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

输出:



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

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

最佳答案

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

只需搜索基数转换，实现从每个“数字”到对应字符的映射，然后简单地执行从0到word_lengthalphabet_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

关于c++ - 如何使用字符串重复生成所有变体？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3026263/