То можно ли хотя бы за полином от
проверить, что группа имеет размер не больше
?
Я, вообще, как к этой проблеме подхожу. Вот у нас есть образующие и соотношения между ними. Будем перечислять элементы группы. Для этого будем строить дерево имён элементов в исходных образующих:
1
a
b
aa
ab
ba
bb
aaa
aab
aba
abb
baa
bab
bba
... и так далее
С одной образующей это будут по одной букве наращиваемые слова, с тремя и более образующими — ситуация анаголична списку выше, только ветвистость будет сильнее. Надеюсь, этот момент понятен.
Теперь на каждом шаге мы должны проверять, не встретился ли нам уже перечисленный элемент, но записанный более длинным или просто другим словом. Для этого, разумеется, надо задействовать соотношения между образующими. Пытаться преобразовать каждое новое слово по отдельности, на мой взгляд, не эффективно. Я даже не знаю, с какой стороны к этой проблеме подойти, если решать её в лоб. Конечно, ранее найденные слова, которые редуцируются к более коротким или просто к словам с меньшим лексикографическим весом, позволят упростить ситуацию до определённой степени. Но каждое такое сокращение потребуется ещё найти, а, как правило, такой поиск включает удлинение слова с помощью групповых соотношений. Полный перебор экспоненциально сложен, а требования остановки на горизонте не видно.
(————————————————————————————————————————————————————————————————)
Я пытаюсь обойти эту проблему широкой свободы возможных действий над словом с помощью предварительной постройки некоторого минимального набора редуцирующих (в лексикографическом смысле) соотношений. Очевидно, что слова в самих этих соотношениях не могут быть дальше редуцированны с помощью них же. Например, для группы
возможен такой набор (не уверен, что он единственный даже для фиксированного множества исходных групповых соотношений):
aab -> ba
bbb -> 1
babb -> aa
bbaa -> abb
bbab == aaaa
abaaa -> b
ababa -> bb
baaaa -> ab
babaa -> abab
aaaaaa -> babab
Исходными здесь являются первые два соотношения в списке, не одно не было удалено в процессе его построения. Используя эти редуцирующие соотношение построение списка элементов будет выглядеть так:
№№ Элем. Наслед. a, b Редуциров.
1 I a b -
2 a aa ab -
3 b ba bb -
4 aa aaa aab -
5 ab aba abb -
6 ba baa bab -
7 bb bba bbb -
8 aaa aaaa aaab -
- aab - - ba
9 aba abaa abab -
10 abb abba abbb -
11 baa baaa baab -
12 bab baba babb -
13 bba bbaa bbab -
- bbb - - I
14 aaaa aaaaa aaaab -
- aaab - - aba
15 abaa abaaa abaab -
16 abab ababa ababb -
17 abba abbaa abbab -
- abbb - - a
18 baaa baaaa baaab -
- baab - - bba
19 baba babaa babab -
- babb - - aa
- bbaa - - abb
- bbab - - aaaa
20 aaaaa aaaaaa aaaaab -
- aaaab - - baa (= aaba)
- abaaa - - b
- abaab - - abba
- ababa - - bb
- ababb - - aaa
- baaaa - - ab
- baaab - - baba
- babaa - - abab
21 babab bababa bababb -
- aaaaaa - - babab
- aaaaab - - abaa (= aaaba)
- bababa - - I (= bbb)
- bababb - - baaa
Алгоритм на этом этапе чрезвычайно прост и прозрачен. Не смотря на то, что здесь фактически выполняется поиск в ширину на дереве, количество просматриваемых узлов графа равно:
где
m — число образующих,
N — порядок группы. Для каждого узла выполняется проверка на редуцируемость. Для этого надо проверить не является ли какой-нибудь
суффикс текущего слова первым словом в каком-нибудь редуцирующем соотношении из списка выше. Тот факт, что
префиксы несократимы гарантируется построением. Это перестаёт быть верным, после первой подстановки суффикса. Однако, эта подстановка гарантированно
уменьшает лексикографический вес слова, поэтому, даже если оно сократимо далее, минимальное имя элемента уже имеется в наличии в частично (на данном этапе) построенном дереве. Чтобы получить конечный результат надо просто пройтись по нему от корня, перебирая буквы слова, полученного подстановкой суффикса. Надо также заметить, что лексикографическое упорядочивание у меня здесь
не как в словаре, а наоборот: сначала смотрится длина слова, а потом уже его алфавитный порядок.
В результате сложность алгоритма является полиномом от порядка группы, числа образующих, максимальной длины слова и количества редуцирующих соотношений в списке, которое может быть как малым, так и большим, но, очевидно, не больше порядка группы. Максимальная длина слова в лучшем случае является (переменные те же, что и выше):
когда большое число элементов группы не коммутирует, и в записи слов встречаются всевозможные комбинации образующих во всевозможных порядках. А в худшем случае (смотри группы
,
,
и так далее для примера):
То есть, не хуже порядка группы.
Надо заметить, что гарантией завершения алгоритма, (так же корректности результата, но его можно проверить постфактум) является корректность исходного набора соотношений. Так что для "защиты от дурака" необходимо добавить остановку при превышении порогов на число найденных элементов и на длину слова.
Каждый элемент в пятом столбце встречается ровно
m раз. Это будет нужно ниже.
(————————————————————————————————————————————————————————————————)
В итоге задача сводится к нахождению минимального списка редуцирующих соотношений. И это то, куда я запрятал всю тяжесть вычислительного труда, потому что необычайный простор для преобразований никуда не делся.
Я пытался сделать этот поиск просто комбинируя пары исходных соотношений из множества, а затем редуцируя их с помощью других представителей этого множества. Тем самым это множество расширяется. Комбинирование двух соотношений выполняется следующим образом. Сначала ищется такая пара, чтобы суффикс одного из слов в одной паре совпадал с префиксом одного из слов в другой паре:
Домножая и делая подстановку получаем:
Результирующее соотношение может дальше упроститься, если
A и
C имеют одинаковый префикс и/или
F и
D — суффикс. После сокращения соотношение дальше редуцируется всевозможным образом с помощью имеющегося набора соотношений. Несократимый результат, если он не является тривиальным "нейтральный элемент равен нейтральному" добавляется в список. Затем проверяться, можно ли имевшиеся ранее в списке соотношения сократить с помощью вновь найденных. Это гарантирует, что список будет минимальным не саморедуцируемым редуцирующим набором соотношений. Требования, необходимые для алгоритма выше.
У этого подхода две проблемы. Первая заключается в том, когда остановиться. Если больше новых соотношений не получается, то хорошо, дело сделано, приступаем ко второму этапу. Однако, часто бывает так, что список соотношений будет расти бесконечно, если ему позволить, а не остановиться когда, например, длина списка и/или длина слова превысит определённый порог. При этом, правда, нет гарантии, что полученный набор соотношений является полным в том смысле, что его использование в алгоритме выше даст группу или вообще он завершится.
Вторая проблема заключается в том, что оказалось, что этого недостаточно. Бывают такие наборы соотношений (сейчас навскидку не помню примеры), когда поиск редуцирующих соотношений завершается, но их набор не является полным. Чтобы побороть эту проблему мне пришлось хранить словарь промежуточных результатов и комбинировать соотношения из этого словаря с соотношениями набора. Редуцирование и пополнение списка редуцирующих соотношений выполняется как и раньше.
И тут возвращается проблема широченного простора возможных действий, только в виде экспоненциально быстро (от длины слова) растущего словаря. Она особенно обостряется тем, что многие тождественные соотношения имеют одинаковую длину. Для иллюстрации проблемы можно рассмотреть групповые соотношения:
Для слова длиной 12 ниже они дают 18 синонимов (не уверен, что список полный, но для примера достаточно):
abbaaaaabbbb
bbabaaaabbba
bbabaaabbaba
bbabaabaabba
bbabaababbaa
bbabaabbaaba
bbabaabbbaaa
bbababaababa
bbababbaaaba
bbababbabaaa
bbabbaaaabba
bbabbaaabbaa
bbabbaabaaba
bbabbaabbaaa
bbabbabaabaa
bbabbabbaaaa
bbabbbaaaaba
bbabbbaabaaa
bbabbbbaaaaa
Если не предпринимать специальных мер, то словарь промежуточных соотношений будет содержать
запись, соответствующую этому набору тождественных слов. И таких случаев
МНОГО, и тем больше, чем длиннее слова. И все они получаются только из пары вышеуказанных. А исходные соотношения в группе могут быть довольно длинными, особенно если используются записи в духе
Если алгоритм перебирает соотношения из словаря в порядке возрастания их лексикографического веса, то просто чтобы добраться до критически важного (но длинного) соотношения придётся совершить неимоверную работу и забить результатом всю имеющуюся оперативку.
Можно, конечно, пытаться бороться с этой проблемой, например, присвоить соотношениям некий потомственный индекс, инкрементируя его для нового соотношения получаемого из старого. А выбор из словаря делать в каком-то хитром режиме, учитывающим как этот индекс, так и лексикографический вес. При этом останется другое следствие проблемы тождества слов: трудоёмость редуцирования каждого нового найденного слова. Потому что для редуцирования его всевозможными способами, необходимо его преобразовать соотношениями равной длины всевозможными способами, иначе есть шанс пропустить нужный результат. В том числе и поэтому, я решил пойти другим путём.
(————————————————————————————————————————————————————————————————)
Я задался вопросом: можно ли вообще редуцировать длинные соотношения как-то более эффективно? Так, чтобы проверка на редуцируемость с помощью редуцирующих соотношений делалась не поиском подстрок и сравнением, как-то
автоматически в процессе. Оказывается, можно: нужно просто воспользоваться графом Кэли группы! Берём слово и буква за буковой следуем вдоль соответствующих рёбер графа.
Всё. Клихэнгер. За три с половиной часа клаважмаканья устал. Опишу текущее состояние дел позже.