Вычисление размера возможностей UID

Ответ 1

В то время как мой другой ответ хорошо заботится об этом конкретном приложении, вот более общий подход. Он заботится о ситуациях, когда у вас есть другое регулярное выражение, описывающее данный язык. Он также позволяет значительно увеличить длину строки, поскольку для вычисления числа комбинаций для строк длиной до n требуется только арифметические операции O (log n). В этом случае количество строк растет настолько быстро, что стоимость этих арифметических операций резко возрастет, но это может быть не так для других, в противном случае подобных ситуаций.

Построить автомат с конечным состоянием

Начните с описания регулярного выражения вашего языка. Переведите это регулярное выражение в конечный автомат. В вашем случае регулярное выражение может быть задано как

(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+

Автомат может выглядеть так:

Устранить ε-переходы

Этот автомат обычно содержит ε-переходы (т.е. переходы состояний, которые не соответствуют ни одному входному символу). Удалите их, так что один переход соответствует одному символу ввода. Затем добавьте ε-переход к принимающему состоянию (состояниям). Если принимающие состояния имеют другие исходящие переходы, не добавляйте к ним ε-петли, а вместо этого добавьте ε-переход в принимающее состояние без исходящих ребер, а затем добавьте к нему цикл. Это можно рассматривать как заполнение входа с ε на его конце, не допуская ε в середине. В совокупности это преобразование гарантирует, что выполнение ровно n переходов состояний соответствует обработке ввода n символов или меньше. Модифицированный автомат может выглядеть так:

Обратите внимание, что оба строительство первого автомата из регулярного выражения и устранение е-переходов может выполняться автоматически (и, возможно, даже в одном шаге. Полученный в результате могли бы автоматы быть сложнее, чем то, что я построил здесь вручную, но принцип тот же.

Обеспечение уникальных путей

Вам не нужно делать автомат deterministic в том смысле, что для каждой комбинации состояния источника и символа ввода есть только одно целевое состояние. Это не тот случай в моей ручной конструкции. Но вы должны убедиться, что каждый полный ввод имеет только один возможный путь к принимающему состоянию, поскольку вы по существу будете считать пути. Создание детерминированного автомата обеспечило бы это более слабое свойство, так что идите на это, если вы не сможете обеспечить уникальные пути без этого. В моем примере длина каждого компонента четко определяет, какой путь использовать, поэтому я не сделал его детерминированным. Но я включил пример с детерминированным подходом в конце этого сообщения.

Матрица перехода на строительство

Затем запишите матрицу перехода. Свяжите строки и столбцы с вашими состояниями (в порядке a, b, c, d, e, f в моем примере). Для каждой стрелки вашего автомата напишите количество символов, включенных в метку этой стрелки в столбце, связанном с исходным состоянием, и строку, связанную с целевым состоянием этой стрелки.

⎛ 0  0  0  0  0  0⎞
⎜ 9 10  0  0  0  0⎟
⎜10 10  0 10 10  0⎟
⎜ 0  0  1  0  0  0⎟
⎜ 0  0  0  9 10  0⎟
⎝ 0  0  0 10 10  1⎠

Считать результат с этой матрицы

Теперь применение этой матрицы с вектором столбца имеет следующее значение: если в входном векторе закодировано количество возможных способов поступления в заданное состояние, выходной вектор дает вам несколько способов перехода один за другим. Возьмите 64-ю степень этой матрицы, сосредоточьтесь на первом столбце (так как ситуация начала старта кодируется как (1,0,0,0,0,0), что означает только один способ закончить в начальном состоянии) и подвести итог все записи, которые соответствуют принимающим состояниям (только в последнем случае). Нижним левым элементом 64-й степени этой матрицы является

1474472506836676237371358967075549167865631190000000000000000000000

который подтверждает мой другой ответ.

Эффективно вычислить мощности матрицы

Чтобы действительно вычислить 64-ю степень этой матрицы, самый простой подход был бы повторен в квадрате: после квадратизации матрицы 6 раз у вас есть показатель 2 ⁶= 64. Если в каком-то другом сценарии ваш показатель (т.е. Максимальная длина строки) не равен двум, вы все равно можете выполнить возведение в степень возведения в квадрат путем умножения соответствующих квадратов в соответствии с битовой диаграммой экспоненты. Именно поэтому этот подход принимает арифметические операции O (log n) для вычисления результата для длины строки n, предполагая фиксированное количество состояний и, следовательно, фиксированную стоимость для каждой квадратичной квадратики.

Пример с детерминированным автоматом

Если вы решили сделать мой автомат детерминированным, используя обычную конструкцию poweret, вы получите

и сортируя состояния как a, bc, c, d, cf, cef, f, получим матрицу перехода

⎛ 0  0  0  0  0  0  0⎞
⎜ 9 10  0  0  0  0  0⎟
⎜ 1  0  0  0  0  0  0⎟
⎜ 0  1  1  0  1  1  0⎟
⎜ 0  0  0  1  0  0  0⎟
⎜ 0  0  0  9  0 10  0⎟
⎝ 0  0  0  0  1  1  1⎠

и мог бы суммировать последние три элемента первого столбца его 64-й степени, чтобы получить тот же результат, что и выше.

Ответ 2

Единый компонент

Начните с поиска способов формирования одного компонента. Соответствующим регулярным выражением для одного компонента является

0|[1-9][0-9]*

так что это либо нуль, либо ненулевая цифра, за которой следует произвольное количество нулевых цифр. (Сначала я пропустил возможный единственный нулевой случай, но комментарий малата дал мне понять об этом.) Если общая длина такого компонента должна быть n, и вы пишете h (n), чтобы обозначить количество способов чтобы сформировать такой компонент длины точно n, тогда вы можете вычислить, что h (n) как

h(n) = if n = 1 then 10 else 9 * 10^(n - 1)

где случай n = 1 допускает все возможные цифры, а другие случаи обеспечивают ненулевую первую цифру.

Один или несколько компонентов

В подразделе 9.1 только написано, что UID представляет собой связку компонентов с разделенными точками, как описано выше. Таким образом, в регулярных выражениях, которые были бы

(0|[1-9][0-9]*)(\.(0|[1-9][0-9]*))*

Предположим, что f (n) - количество способов записи UID длины n. Тогда у вас есть

f(n) = h(n) + sum h(i) * f(n-i-1) for i from 1 to n-2

Первый термин описывает случай единственного компонента, а сумма позаботится о случае, когда он состоит из более чем одного компонента. В этом случае у вас есть первый компонент длины i, затем точка, которая учитывает -1 в формуле, а затем остальные цифры образуют один или несколько компонентов, которые выражаются через рекурсивное использование f.

Два или более компонента

Как указывает комментарий cneller, часть раздела 9 перед подразделом 9.1 указывает, что должно быть не менее двух компонентов. Поэтому правильное регулярное выражение будет больше похоже на

(0|[1-9][0-9]*)(\.(0|[1-9][0-9]*))+

с + в конце, указывающим, что мы хотим хотя бы одно повторение выражения в скобках. Вывод выражения для этого просто означает отказ от однокомпонентного случая в определении f:

g(n) = sum h(i) * f(n-i-1) for i from 1 to n-2

Если вы суммируете все g (n) для n из 3 (минимальная возможная длина UID) до 64, вы получаете количество возможных UID как

1474472506836676237371358967075549167865631190000000000000000000000

или приблизительно 1.5e66. Это значительно меньше, чем 4.5e66, которое вы получаете от своих вычислений, с точки зрения абсолютной разницы, хотя и определенно на одном уровне. Кстати, в вашей оценке явно не упоминаются UID короче 64, но вы всегда можете рассмотреть возможность заполнения их точками в настройках. Я вычислил с помощью несколько строк кода Python:

f = [0]
g = [0]
h = [0, 10] + [9 * (10**(n-1)) for n in range(2, 65)]
s = 0
for n in range(1, 65):
    x = 0
    if n >= 3:
        for i in range(1, n - 1):
            x += h[i] * f[n-i-1]
    g.append(x)
    f.append(x + h[n])
    s += x
print(h)
print(f)
print(g)
print(s)