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

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 baa baab baba babb bba bbab bbba bbbb

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

这是出于学习目的,它不是功课.我希望我的作业就是这样.

Answer 1

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

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

这种算法应该与使用恒定存储量需要产生的字符串数量成线性地成比例地运行.

用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