Математика: Комбинаторика и перебор.

Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово

Данная задача, в общем-то не требует особого алгоритма. Я помещаю здесь ее решение, чтобы показать, как можно рассуждать, если не требуется напечатать все слова, а только узнать их число.

Простой случай

Элементы исходной последовательности-алфавита различны, слово зависит от порядка букв. Если в исходной последовательности есть одинаковые буквы, то надо будет кое-что подкорректировать (их-то порядок не важен будет в слове, если стоят рядом).

По идее всего слов размера К из N букв будет... хмм... из 1-й буквы N возможных из двух N²... - для каждой первой буквы N возможных слов... в общем из К -

(1) N^k.

Из этого надо вычесть все последовательности, содержащие данную подпоследовательность. Сколько таких?

Хмм... Што там у нас было на теорвере... Вай мозги не работают :(... Пусть длина плохой подпоследовательности m. Ищем все подпоследовательности длины к с фикс. частью длины m.

   Пусть фикс. часть в начале
  <--фиксированная часть слова--><--можем менять-->
             m букв                     k-m

Возможностей для изменения - n^(k-m). Далее можно сдвинуть k-m раз вправо сию фикс. часть, получив таким образом еще (k-m)*n^(k-m) слов. Тогда всего возможно

(2) (k-m+1)*n^(k-m)

слов длины К из Н букв, содержащих данную подпоследовательность длины м.

Вычитаем (2) из (1) - получаем искомое число.

Сложный случай

Если же есть одинаковые буквы, то подсчет будет посложнее. Тебе понадобится подсчитать количество групп одинаковых букв и их количество в каждой (например, 3 буквы н и 2 буквы а в исходной последовательности - это 2 группы: по 3 и 2 элемента), затем для простоты сначала получить число (В) - ВСЕХ подпоследовательностей из К букв содержащих первую группу - то есть в которых она фиксирована.
- поделить это число на число комбинаций элементов в группе - тогда увидишь число РАЗЛИЧНЫХ таких подпоследовательностей (то есть различных слов),
вычесть это число РАЗЛИЧНЫХ из числа (В) ВСЕХ с первой группой - получили лишние слова, а затем вычесть результат из (1) - вообще всех слов.

И так для всех групп. Окончательно получим нечто меньшее n^k - число ВСЕХ РАЗЛИЧНЫХ слов из К букв N-буквенной последовательности-алфавита.

Аналогичным образом поступить с числом слов, содержащих плохую подпоследовательность, превратив это число в число РАЗЛИЧНЫХ слов.

И вычесть, как и в простом случае это число, уже меньшее (2) из всех чисел (1). Возможно, такое решение, где все подсчитывается отдельно несколько неоптимально, но оно просто, очевидно, а, главное, должно работать.

Вверх по странице, к оглавлению и навигации.