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

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) 时，我感到很困惑。

我找到了这个 Whosebug question 但是接受的答案生成了长度为 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();

}

请注意，此算法的运行时间及其 returns 的数据量随着长度的增加呈指数增长，这意味着如果您的长度很大，您应该期望代码需要很长时间和 return 大量数据。

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" 和 "c" 作为允许的字符，您以 3 为基数进行计数，并且由于您允许三个字符串，因此它们是三位数数字。

以 M 为基数的 N 位数字可以表示 N^M 个不同的可能值，从 0 到 N^M-1。因此，对于您的情况，那是 limit=pow(3, 3)-1;。要生成所有这些值，您只需从 0 计数到极限，然后将每个数字转换为基数 M，使用指定的字符作为 "digits"。例如，在 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";
    }
}

一个小注意事项：正如我在此处所写的那样，这基本上以小端格式生成输出。即左边变化最快的"digit"，右边变化最慢的

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

Dynamic character generator; Generate all possible strings from a character set

string

for-loop

language-agnostic

dynamically-generated

打印：