c++ - 找出字母表 {a, b, c} 中长度为 n 的字符串 w 的数量

Question

我想弄清楚如何计算所有长度为 n 的字符串的数量，使得字符串 w 的任何长度为 4 的子字符串，所有三个字母 a、b、c 都出现。例如，当 n = 9 时应打印 abbcaabca，但不应包含 aabbcabac。

我想做一个像这样的数学公式

3^N - 3 * 2^N + 3 or (3^(N-3))*N!

它可以这样工作吗，还是我必须生成它们并计算它们？我正在处理像 100 这样的大数字，但我认为我无法生成它们来计算它们。

Answer 1

您可能应该能够按照自己的方式努力，从让我们说出所有可能的长度为 4 的单词开始，然后只添加一个字母并计算可能允许的结果单词。然后您可以迭代地增加到更高的数字，而不必探索所有 3^N 种可能性。

const unsigned w = 4;
unsigned n = 10;

vector<string> before,current;

// obtain all possible permutations of the strings "aabc", "abbc" and "abcc"
string base = "aabc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);
base = "abbc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);
base = "abcc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);

// iteratively add single letters to the words in the collection and add if it is a valid word
size_t posa,posb,posc;
for (unsigned k=1;k<n-w;++k)
{
    current.clear();
    for (const auto& it : before)
    {
        posa = it.find("a",k);
        posb = it.find("b",k);
        posc = it.find("c",k);
        if (posb!= string::npos && posc!= string::npos) current.emplace_back(it+"a");
        if (posa!= string::npos && posc!= string::npos) current.emplace_back(it+"b");
        if (posa!= string::npos && posb!= string::npos) current.emplace_back(it+"c");
    }
    before = current;
}
for (const auto& it : current) cout<<it<<endl;
cout<<current.size()<<" valid words of length "<<n<<endl;

请注意，使用这个你仍然会很快遇到指数墙......在更有效的实现中，我会将单词表示为整数(不是整数 vector ，而是以 3 为底的表示形式的整数)，但是指数缩放仍然存在。如果您只对数字感兴趣，@Jeffrey 的方法肯定更好。