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


c++ computation-theory alphabet
person brynello    schedule 24.03.2016    source источник
comment
Это не направлено на ОП. Почему этот вопрос действителен, несмотря на то, что не содержит ни кода, ни попыток решить проблему, а только то, что явно является домашним заданием? Это неправильный вопрос SO.   -  person Nathaniel Johnson    schedule 24.03.2016
comment
Действительно, это комбинаторика.   -  person Darkdragon84    schedule 25.03.2016

Ответы (2)


arrow_upward
1
arrow_downward

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

person Darkdragon84    schedule 24.03.2016
comment
Если у вас есть строка длины k-1, вы можете сгенерировать соответствующие строки длины k. Если последние 3 символа содержат все буквы a, b, c, вы можете добавить либо a, b, либо c; если нет, вы добавляете только символ 4 с конца. Это не будет расти слишком быстро. Есть 27 комбинаций из трех символов, но «aaa», «bbb» и «ccc» не могут появиться, так что это 24 возможности. Из них только шесть позволяют выбрать три варианта. Я думаю, что это дает средний коэффициент роста 1,31 (и в сотой степени это примерно 1E12). Есть только 36 строк длины 4 для начала. - person Martin Bonner supports Monica; 24.03.2016
comment
Я думаю, что для начала должно быть 72 строки длины 4: 3*4! = 3*4*3*2 = 8*9 = 72. - person Darkdragon84; 24.03.2016
comment
Почему «3*4!»? Моей первоначальной мыслью было шесть способов упорядочить «abc» и четыре места для добавления любого из трех символов => 6 * 4 * 3 (= 72). Но это включает в себя много двойного счета => например, aabc может быть «Xabc» или «aXbc», где X — это дополнительный символ, который мы добавляем, чтобы довести счет до четырех. В конце концов я сгенерировал все 3 ^ 4 строки в Excel и подсчитал те, которые содержали все три символа. - person Martin Bonner supports Monica; 24.03.2016
comment
В самом деле, мы должны смотреть на слова вида «Xabc». Давайте сначала посмотрим на X=a. Затем нам потребуются все возможные перестановки «aabc», а их действительно не 4! = 24, а 4!/2 = 12 из них, так как два элемента одинаковы (поэтому мы должны делить на 2). Далее мы рассмотрим X=b и X=c, то есть все возможные перестановки 'abbc' и 'abcc'. - person Darkdragon84; 25.03.2016
comment
Тогда это 3 различных набора, где ни один элемент одного набора не может появиться в другом, и всего мы получаем 3 * 4!/2 = 36 допустимых слов длины 4, вы правы. Извините, я упустил из виду тот факт, что вы должны делить на 2, так как порядок двух одинаковых букв не имеет значения :-) Однако моя вышеприведенная программа дает правильный начальный набор. - person Darkdragon84; 25.03.2016

arrow_upward
0
arrow_downward

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

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

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

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

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

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

person Jeffrey    schedule 24.03.2016
comment
Я предполагаю, что вам все равно придется начинать с некоторого конечного начального значения, а затем двигаться вверх. Тогда вы получите последовательность x[n+k] = \sum_{l=0...k-1} a_l x[n+l]. Затем вы можете посмотреть на предел x{n+1]/x[n], чтобы получить показатель масштабирования для n больших. - person Darkdragon84; 25.03.2016