Найти количество строк w длины n в алфавите {a, b, c}
Я пытаюсь выяснить, как рассчитать количество всех строк длины n, так что любая подстрока длиной 4 строки w, все три буквы a, b, c встречаются. Например, abbcaabca должен быть напечатан, когда n = 9, но aabbcabac не должен быть включен.
Я пытался сделать математическую формулу, как
3^N - 3 * 2^N + 3 or (3^(N-3))*N!
Это может работать таким образом, или я должен генерировать их и считать их? Я работаю с большими числами, такими как 100, и я не думаю, что смогу сгенерировать их для подсчета.
Решение
Хитрость заключается в том, чтобы решить проблему. Рассматривать:
Поможет ли знать, сколько таких строк длиной 50, заканчивающихся в каждой паре букв?
Количество 50-строк, оканчивающихся на AA раз
Номер 50-струнный, начиная с B или C
+
Количество 50-строк, оканчивающихся на AB раз
Номер 50-струнный, начиная с C
+
Все остальные комбинации дают вам количество 100-длинных строк.
Продолжайте разбирать его рекурсивно.
Посмотрите динамическое программирование.
Также ищите большое количество библиотек.
Другие решения
Вы, вероятно, должны быть в состоянии продвинуться вверх и начать, скажем, со всех возможных слов длины 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;
Обратите внимание, что при этом вы все равно довольно быстро столкнетесь с экспоненциальной стеной … В более эффективной реализации я представлял бы слова как целые числа (НЕ векторы целых, а скорее целые числа в представлении с основанием 3), но экспоненциальное масштабирование все еще там. Если вас просто интересует число, подход @ Джеффри, безусловно, лучше.
detector