Параметрическое слово

В математическом изучении комбинаторики слов параметрическое слово представляет собой строку в заданном алфавите, имеющую некоторое количество подстановочных знаков . Набор строк, соответствующих данному параметрическому слову, называется набором параметров или комбинаторным кубом . Слова-параметры можно составлять для создания подкубов меньшего размера данного комбинаторного куба. Они имеют применение в теории Рамсея и в информатике для обнаружения дублированного кода .

Определения и обозначения

Формально $k$-параметрическое слово длины $n$, по заданному алфавиту $A$, представляет собой последовательность $n$ персонажи, некоторые из которых могут быть взяты из $A$ и другие из которых $k$ отдельные символы подстановки $*_{1},*_{2},\ldots ,*_{k}$. Каждый подстановочный знак должен появляться хотя бы один раз, но может появляться несколько раз, а подстановочные знаки должны появляться в порядке, заданном их индексами: первый подстановочный знак в слове должен быть $*_{1}$, следующий, который отличается от $*_{1}$ должно быть $*_{2}$и т. д. В частном случае слово над данным Алфавит без каких-либо подстановочных знаков называется словом с 0 параметрами. Для слов с 1 параметром индексы могут быть опущены, поскольку между различными подстановочными знаками нет неоднозначности. Набор всего $k$-параметрические слова закончились $A$, длины $n$, обозначается $A{\tbinom {n}{k}}$.

А $k$-слово параметра представляет собой набор $|A|^{k}$ строки (слова с 0 параметрами), полученные заменой символа $A$ для каждого подстановочного знака. Этот набор строк называется набором параметров комбинаторного куба , и $k$ называется его размерностью. Одномерный комбинаторный куб можно назвать комбинаторной прямой .

В комбинаторном кубе каждая копия определенного подстановочного знака должна иметь одинаковую замену. Обобщение слов-параметров позволяет контролируемым образом заменять разные копии одного и того же подстановочного знака разными символами алфавита. Если $A$ это алфавит и $G$ это группа с действием на $A$, тогда $G$Слово параметра с меткой - это $k$-слово -параметр вместе с присвоением элемента группы каждому подстановочному знаку в слове. Первому появлению каждого подстановочного знака должен быть присвоен идентификационный элемент группы. Затем строки, представленные помеченным параметрическим словом, получаются путем выбора символа $A$ для каждого подстановочного знака и замены результата объединения этого символа элементом группы, маркирующим каждую копию этого символа. Набор всего $G$-маркированный $k$-параметрические слова закончились $A$, длины $n$, обозначается $[A,G]{\tbinom {n}{k}}$.

Пример

В игре крестики-нолики клеткам игрового поля можно задать две целочисленные координаты. $(x,y)$ из алфавита $\{1,2,3\}$. Объединение этих двух координат дает строку, представляющую каждую ячейку, одну из девяти строк. $11,12,13,21,22,23,31,32,$ или $33$. В этом алфавите есть семь однопараметрических слов длины два, слова $1*,2*,3*,*1,*2,*3,$ и $**$. Соответствующие комбинаторные линии образуют семь из восьми строк по три клетки в ряд на доске «крестики-нолики»; например, однопараметрическое слово $2*$ соответствует комбинаторной прямой $\{21,22,23\}$, и однопараметрическое слово $**$ соответствует комбинаторной прямой $\{11,22,33\}$.

Однако в этом наборе комбинаторных линий отсутствует одна из восьми выигрышных линий игры «крестики-нолики»: антидиагональная линия. $\{13,22,31\}$. Эту строку можно получить как комбинаторную строку (без включения каких-либо других комбинаций ячеек, которые были бы недопустимы для крестиков-ноликов), используя группу из двух элементов и действие, в котором неидентичный элемент меняет местами буквы алфавита $1$ и $3$ покидая элемент $2$ на месте. Для этого действия имеется восемь помеченных однопараметрических слов длиной два, семь из которых получаются из непомеченных однопараметрических слов с использованием идентификационной метки для всех подстановочных знаков. Эти семь имеют те же комбинаторные линии, что и раньше. Восьмое помеченное слово состоит из слова $**$ помеченный идентификационным элементом для своего первого $*$ и реверсивный неидентичный элемент для второго $*$; его комбинаторная линия является последней выигрышной линией на доске для игры в крестики-нолики, $\{13,22,31\}$.

Состав

Для трех заданных целочисленных параметров $n\geq m\geq k$, можно объединить два слова параметра, $f\in A{\tbinom {n}{m}}$ и $g\in A{\tbinom {m}{k}}$, чтобы создать другое слово параметра $f\circ g\in A{\tbinom {n}{k}}$. Для этого просто замените каждую копию $i$й подстановочный знак в $f$ по $i$персонаж в $g$. Это обязательно приведет к созданию слова длиной $n$ который использует каждый из подстановочных символов в $g$ хотя бы один раз, в порядке возрастания, чтобы получить действительный результат $k$-параметрическое слово длины $n$. Это понятие композиции также можно распространить на композицию помеченных слов-параметров (использующих один и тот же алфавит и групповое действие), применяя групповое действие к заменяемым символам без подстановочных знаков и создавая групповые метки для заменяемых подстановочных знаков. Подмножеством комбинаторного куба является комбинаторный куб меньшего размера, если его можно получить композицией таким способом.

Комбинаторное перечисление

Количество слов параметров в $A{\tbinom {n}{k}}$ для алфавита размером $r$ это $r$- число Стирлинга второго рода. $\textstyle \left\{{r+n \atop r+k}\right\}_{r}$. Эти числа подсчитывают количество разделов целых чисел в диапазоне $[1,r+n]$ в $r+k$ непустые подмножества такие, что первое $r$ целые числа принадлежат к разным подмножествам. Разделы этого типа можно привести в биективную эквивалентность со словами-параметрами, создав слово с символом для каждого из $n$ целые числа в диапазоне $[r+1,n+r]$,установка этого значения символа как целое число в $[1,r]$ принадлежащий одному и тому же подмножеству раздела, или подстановочный знак для каждого подмножества раздела, который не содержит целое число в $[1,r]$. $r$-Числа Стирлинга подчиняются простому рекуррентному соотношению, с помощью которого их можно легко вычислить.

Приложения

В теории Рамсея параметрические слова и комбинаторные кубы могут использоваться для формулировки теоремы Грэма-Ротшильда , согласно которой для каждого конечного алфавита и группового действия, а также каждой комбинации целочисленных значений $m$, $k$, и $r$, существует достаточно большое количество $n$ такое, что если каждый $k$-мерный комбинаторный куб над строками длины $n$ присваивается один из $r$ цвета, то существует $m$-мерный комбинаторный куб, все $k$-мерные подкубы имеют одинаковый цвет. Этот результат является ключевой основой структурной теории Рамсея и используется для определения числа Грэма — огромного числа, используемого для оценки значения $n$ для определенной комбинации значений.

В информатике , в задаче поиска дубликатов кода ,исходный код данной процедуры или модуля может быть преобразован в слово параметра путем преобразования его в последовательность токенов ,и для каждого имени переменной или подпрограммы заменять каждую копию одного и того же имени одним и тем же подстановочным знаком. Если код дублируется, результирующие слова параметров останутся равными, даже если некоторые переменные или подпрограммы были переименованы. Более сложные алгоритмы поиска могут находить длинные повторяющиеся разделы кода, которые образуют подстроки в более крупных репозиториях исходного кода, позволяя заменять друг друга подстановочными знаками.

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

См. также

• Регулярное выражение