如何通过重复字符串生成所有变体？
如何通过重复字符串生成所有变体？
提问于 2018-12-05 01:54:27
我想用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
输出：
下载abbas abbas baasi baab bbaa bbba bbb
理想情况下，我想要一个可以产生精确输出的C ++程序，采用完全相同的参数。
回答 2
Stack Overflow用户
发布于 2018-12-05 10:03:49
您可以将其视为计数，其基数等于字母表中的字符数（如果这是可能的输入，则特别注意字母表中的多个相等字符）。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
Stack Overflow用户
发布于 2018-12-05 11:12:52
这里是一般材料，而不是特定于实现产品的C ++：
取产品输入字符串“abc ..”生成矩阵“abc ..”x“abc ..”。 N ^ 2的复杂性。 表示矩阵为向量，重复乘以“abc”，复杂度（N ^ 2）* N，重复。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100000908
复制相关文章
相似问题