Как рассчитать количество возможных наборов строк с элементами разных длин? - PullRequest
Новая
       10

Как рассчитать количество возможных наборов строк с элементами разных длин?

0 голосов
/ 06 января 2019

Мне нужно написать алгоритм, который вычисляет количество возможных строк с учетом некоторых ограничений: 

The strings must have an N amount of characters;
The strings only have an X number of different letters;
The strings can't have an Y number of digraphs;

Например, для N = 2, X = 3 и Y = 6: 

The string: _ _ _
My set of letters: {a, b, c}
Set of proibited digraphs: {aa, bb, cc, ab, ac, bc}
#The proper result is 1, but I'm getting -9

Пока мой код работает правильно только тогда, когда длина строки равна 2. У меня не получается создать уравнение, которое охватывает все случаи. Я не могу сделать алгоритм грубой силы, потому что длина строки может иметь любое значение ниже, чем 10 ^ 9

Это мой код: 

def  arrangements(sizeOfSet, numberOfElements, isDigraph):

  if isDigraph:
    return pow(numberOfElements, sizeOfSet - 1)
    #sizeOfSet is subtracted by 1 cause digraphs occupies 2 spaces

  return pow(numberOfElements, sizeOfSet)

И затем я вычитаю аранжировки моего набора букв из аранжировок набора запрещенных диграфов.

1 Ответ

0 голосов
/ 07 января 2019

Это своего рода комментарий, но он слишком велик для комментария.

К сожалению, я не думаю, что вы можете решить эту проблему в виде алгоритма с N, X и Y в качестве входных данных, потому что этих данных недостаточно. Вам нужен фактический набор орграфов, а не его размер.

Рассмотрим две похожие проблемы. Оба имеют алфавит из 2 букв (a, b) и N = 3, но наборы запрещенных орграфов различны.

Задача № 1

Мы запрещаем aa и ab. Итак, все допустимые триплеты:

  • baa
  • bba
  • bbb

Итак, есть 3 решения

Задача № 2

Мы запрещаем aa и bb. Итак, все допустимые триплеты:

  • aba
  • bab

Есть только 2 решения.

Это происходит потому, что орграфы aa и ab взаимодействуют иначе, чем орграфы aa и bb. В частности, триплет не отфильтровывается как aa, так и bb одновременно, но триплет aab отфильтровывается как aa, так и ab, поэтому эффективно отфильтровывается еще один триплет.

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

Обновление (эскиз алгоритма)

Давайте попробуем решить ее как проблему динамического программирования по всей длине строки. То, что мы хотим сохранить как состояние, это количество строк, оканчивающихся на каждый символ (таким образом, массив размером X или словарь того же размера). Если мы найдем способ обновить такое состояние для каждого следующего размера строки, то когда мы доберемся до N, мы можем просто суммировать значения по массиву, и это будет наш окончательный ответ.

Обновление состояния легко. Давайте рассмотрим, что происходит, когда мы добавляем новый символ в допустимую строку длиной n-1. Мы получаем новую действительную строку длиной n, если только последняя пара не является одним из запрещенных орграфов. Таким образом, создание нового состояния легко (вот псевдокод в стиле Python): 

for prev_last_char in chars:
    for new_last_char in chars:
        if (prev_last_char, new_last_char) not in prohibited: 
             new_state[new_last_char] += old_state[prev_last_char]

Очевидно, что начальным состоянием является массив (или словарь), заполненный 1 для каждого символа.

Предполагая, что prohibited время доступа равно O(1), что должно быть достигнуто с помощью словаря на основе хеша, сложность одного шага составляет O(X*X). Таким образом, общая сложность алгоритма составляет O(X^2*N).

...