Вводится конечное задание конечной группы в формате слово=слово … слово=слово, где слово — произвольное сочетание не более, чем четырёх букв x и у (понимаемое как применение бинарной операции к соответствующим буквам) или нейтральный элемент группы e. Вывести все слова — элементы группы. Из множества возможных представлений элемента выбирается лексикографически наименьший среди самых коротких (см. комментарий к примеру). При выводе элементы упорядочить по длине, а элементы одинаковой длины — лексикографически.

Данные вводятся правильные, проверять, что задана именно конечная группа, не надо :) .

xx=yy xxxx=e xyx=y

e x y xx xy yx xxx xxy

Пояснение: злемент xxy можно представить как yyy, но это лексикографически больше xxy; можно представить как xxxyx, но это длиннее, чем xxy.

Я решал задачу так. Начнём с множества атомарных слов x и y. Для каждого из слов xx, xy, yx и yy с помощью производящих правил надо сгенерировать все возможные слова, а затем выбрать наименьшее (по указанному критерию). Получается набор слов, которые сократить уже нельзя. Повторяем процедуру для каждого слова из набора. Если на очередном шаге набор слов не изменился (любое порождаемое слово можно сократить до уже известного), этот набор и есть искомая группа.

Загвоздка только в том, что всех возможных слов бесконечно много :) . Предположительно (обоснование?) любое слово длиннее 4*4=16 букв можно при данных ограничениях сократить (иначе группа бесконечна), поэтому рассматривать такие слова смысла нет.

Сильно ускоряет алгоритм «кеширование» слов, для которых уже найдено наименьшее, в словаре.

«Таблица умножения» для группы:

  8|   e   x  xx xxx xxy  xy   y  yx
------------------------------------
  e|   e   x  xx xxx xxy  xy   y  yx
  x|   x  xx xxx   e  xy   y  yx xxy
 xx|  xx xxx   e   x   y  yx xxy  xy
xxx| xxx   e   x  xx  yx xxy  xy   y
xxy| xxy  yx   y  xy  xx   x   e xxx
 xy|  xy xxy  yx   y xxx  xx   x   e
  y|   y  xy xxy  yx   e xxx  xx   x
 yx|  yx   y  xy xxy   x   e xxx  xx

Примеры преобразования элементов:

xxyyxx → xxxxxx → xx
xyxyxy → xyyy → xyxx → yx
xyyyxxxyy → xyyyxxxxx → xxxyxxxxx → xxyxxxx → xxy
xyyyxxxyyx → xyxxxxxyyx → xyxxxxxxxx → xyxxxx → xy
xyyyxxxyyxy → xyxxxxxyyxy → xyxyyxy → xyxxxxy → xyy → xxx
xyyyxxxyyxyy → xyyyxxxxxxyy → xyyyxxyy → xyxxxxyy → xyxxxxxx → yxxxxx → yx
xyyyxxxyyxyx → xyyyxxxxxxyx → xyxxxxxxxxyx → xyxxxxyx → xyyx → xxxx → e


CategoryHomework

LecturesCMC/PythonIntro2017/Homework_GroupFinite (последним исправлял пользователь FrBrGeorge 2018-01-14 00:51:15)