动态字符生成器;从字符集生成所有可能的字符串

Question

我想制作一个动态字符串生成器，它将从具有动态长度的字符集生成所有可能的唯一字符串。

我可以很容易地使用for循环，但是它的长度是静态的，而不是动态的。

// Prints all possible strings with the length of 3
for a in allowedCharacters {
    for b in allowedCharacters {
        for c in allowedCharacters {
            println(a+b+c)
        }
    }
}

但是当我想让这个长度是动态的我可以把它叫做generate(length: 5)，我就糊涂了

我发现了这个Stackoverflow问题，但是接受的答案生成字符串1-maxLength长度，我想要maxLength在每个字符串上。

Answer 1

如上所述，使用递归。下面是如何用c#完成的:

static IEnumerable<string> Generate(int length, char[] allowed_chars)
{
    if (length == 1)
    {
        foreach (char c in allowed_chars)
            yield return c.ToString();
    }
    else
    {
        var sub_strings = Generate(length - 1, allowed_chars);
        foreach (char c in allowed_chars)
        {
            foreach (string sub in sub_strings)
            {
                yield return c + sub;
            }
        }
    }
}
private static void Main(string[] args)
{
    string chars = "abc";
    List<string> result = Generate(3, chars.ToCharArray()).ToList();
}

请注意，这个算法的运行时间和它返回的数据量随着长度的增加呈指数增长，这意味着如果你有很长的长度，你应该期望代码花费很长时间并返回大量的数据。

Answer 2

@YacoubMassad的c#代码到Swift的翻译:

func generate(length: Int, allowedChars: [String]) -> [String] {
    if length == 1 {
        return allowedChars
    }
    else {
        let subStrings = generate(length - 1, allowedChars: allowedChars)
        var arr = [String]()
        for c in allowedChars {
            for sub in subStrings {
                arr.append(c + sub)
            }
        }
        return arr
    }
}
println(generate(3, allowedChars: ["a", "b", "c"]))

<标题>打印:

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 3

虽然可以(显然足够)使用递归来解决这个问题，但这是一种相当低效的方法。

你真正在做的只是数数。在你的例子中，"a"，"b"one_answers"c"作为允许的字符，你以3为基数计数，因为你允许三个字符串，它们是三位数。

以M为基数的N位数字可以表示N^M个不同的可能值，从0到N^M-1。对于你的例子，这是limit=pow(3, 3)-1;。要生成所有这些值，您只需从0到极限数，并将每个数字转换为基数M，使用指定的字符作为"数字"。例如，在c++中，代码看起来像这样:

#include <string>
#include <iostream>
int main() { 
    std::string letters = "abc";
    std::size_t base = letters.length();
    std::size_t digits = 3;
    int limit = pow(base, digits);
    for (int i = 0; i < limit; i++) {
        int in = i;
        for (int j = 0; j < digits; j++) {
            std::cout << letters[in%base];
            in /= base;
        }
        std::cout << "t";
    }
}

一个小注意事项:正如我在这里所写的那样，这基本上以小端格式生成输出。也就是说，变化最快的"数字"在左边，变化最慢的"数字"在右边。