Найти количество строк 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, и я не думаю, что смогу сгенерировать их для подсчета.

2

Решение

Хитрость заключается в том, чтобы решить проблему. Рассматривать:

Поможет ли знать, сколько таких строк длиной 50, заканчивающихся в каждой паре букв?

Количество 50-строк, оканчивающихся на AA раз
Номер 50-струнный, начиная с B или C
+
Количество 50-строк, оканчивающихся на AB раз
Номер 50-струнный, начиная с C
+
Все остальные комбинации дают вам количество 100-длинных строк.

Продолжайте разбирать его рекурсивно.

Посмотрите динамическое программирование.

Также ищите большое количество библиотек.

0

Другие решения

Вы, вероятно, должны быть в состоянии продвинуться вверх и начать, скажем, со всех возможных слов длины 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), но экспоненциальное масштабирование все еще там. Если вас просто интересует число, подход @ Джеффри, безусловно, лучше.

0

По вопросам рекламы [email protected]