Как определить количество возможных комбинаций букв, которые содержат вырожденную подстроку - PullRequest
Новая
       21

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

0 голосов
/ 15 октября 2018

Я несколько дней ломал голову над тем, чтобы выработать уравнение для ряда или замкнутой формы для решения следующей задачи:

В частности: учитывая все строки длины N который рисует из алфавита из L букв (начиная с 'A', например, {A, B}, {A, B, C}, ...), сколько из этих строк содержит подстрокукоторый соответствует шаблону: «А», более 1 не-«А», «А».Стандартное регулярное выражение для этого шаблона будет A[^A][^A]+A.

. Число возможных строк достаточно простое: L ^ N .Для небольших значений N и L также очень удобно просто создавать все возможные комбинации и использовать регулярное выражение для поиска подстрок, соответствующих шаблону;в R: 

all.combinations <- function(N, L) {
    apply(
        expand.grid(rep(list(LETTERS[1:L]), N)),
        1,
        paste,
        collapse = ''
    )
}

matching.pattern <- function(N, L, pattern = 'A[^A][^A]+A') {
    sum(grepl(pattern, all.combinations(N, L)))
}

all.combinations(4, 2)
matching.pattern(4, 2)

я придумал следующее, которое работает для N <7: </p> 

M <- function(N, L) {
    sum(
        sapply(
            2:(N-2),
            function(g) {
                (N - g - 1) * (L - 1) ** g * L ** (N - g - 2)
            }
        )
    )
}

К сожалению, это работает только тогда, когда N <7, потому что это просто добавлениекомбинации, которые имеют подстроки A..A, A ... A, A .... A и т. д., и некоторые комбинации, очевидно, имеют несколько совпадающих подстрок (например, A..A..A, A..A ...А), которые учитываются дважды. </p>

Есть предложения?Я также открыт к процедурным решениям, если они не зависят от количества комбинаций (как мой код выше).Я хотел бы иметь возможность вычислить для значений N от 15 до 25 и L от 2 до 10.

Для чего это стоит, вот количество комбинаций и соответствующие комбинации для некоторых значений Nи L, которые можно определить путем генерации всех комбинаций и сопоставления с регулярным выражением: 

 N  L  combinations  matching
--  -  ------------  --------
 4  2            16         1
 5  2            32         5
 6  2            64        17
 7  2           128        48
 8  2           256       122
 9  2           512       290
10  2          1024       659
 4  3            81         4
 5  3           243        32
 6  3           729       172
 7  3          2187       760
 8  3          6561      2996
 9  3         19683     10960
10  3         59049     38076
 4  4           256         9
 5  4          1024        99
 6  4          4096       729
 7  4         16384      4410
 8  4         65536     23778
 9  4        262144    118854
10  4       1048576    563499

1 Ответ

0 голосов
/ 21 октября 2018

Можно использовать подход динамического программирования.

Для фиксированных L, пусть X(n) будет числом строк длины n, которые содержат данный шаблон, и пусть A(n) будет числомстроки длиной n, которые содержат заданный шаблон и начинаются с A.

Сначала вывести формулу рекурсии для A(n).Давайте посчитаем все строки в A(n), сгруппировав их по первым 2-3 буквам.Количество строк в A(n) с:

  • "вторая буква A" равна A(n-1),
  • "вторая буква не-A и третья буква A" равна A(n-2),
  • "вторая и третья буква не-A" равна (L^(n-3) - (L-1)^(n-3)).Это потому, что строка «нуждается» по крайней мере в одной букве A для подсчета оставшихся букв.

При этом: 

A(n) = A(n-1) + (L-1) * (A(n-2) + (L-1) * (L^(n-3) - (L-1)^(n-3)))

Строка длины n+1 может начинаться с A илине-A: 

X(n+1) = A(n+1) + (L-1) * X(n)
X(i) = A(i) = 0, for i <= 3

Реализация Python: 

def combs(l, n):
    x = [0] * (n + 1)  # First element is not used, easier indexing
    a = [0] * (n + 1)
    for i in range(4, n+1):
        a[i] = a[i-1] + (l-1) * (a[i-2] + (l-1) * (l**(i-3) - (l-1)**(i-3)))
        x[i] = a[i] + (l-1) * x[i-1]
    return x[4:]

print(combs(2, 10))
print(combs(3, 10))
print(combs(4, 10))
...