Как получить все алгебраические ассоциативные операции на конечном множестве эффективным алгоритмом?

Число двоичных операций на множестве из 2 элементов составляет 2^(2*2)=16.   enter image description here
Число ассоциативной двоичной операции на этом множестве равно 8. enter image description here
Число бинарных операций на множестве из трех элементов равно 3 ^ (3 * 3) = 19683.
Число ассоциативных двоичных операций на этом множестве составляет всего 113. Как узнать, сколько ассоциативных двоичных операций имеется в наборе из n элементов?

Также, чтобы получить все эти 113 операций и записать в файл, необходимо написать программу.
если я попытаюсь получить все операции 19683, а затем проверить его ассоциативное свойство "a * (bc) == (ab) * c" для всех операций 19683 года, это будет работать, но это займет много времени для n = 4 элементы!
Как написать эффективный алгоритм для решения этой задачи?
Пожалуйста, помогите мне!

Ответы

Ответ 1

Больше, чем разработка собственного алгоритма, это задача для поиска математической модели. Для этой задачи я особенно рекомендовал mace4, какую часть библиотеки LADR. Он специально настроен на такие алгебраические проблемы. Вход (пусть назовите его semigroups.in) будет выглядеть так:

formulas(sos).
  (x * y) * z = x * (y * z).
end_of_list.

И затем запустите его mace4 -n 4 -N 4 -m 10000 <semigroup.in (найдите все 4-элементные модели и напечатайте до 10000 из них) производит длинный вывод, например

...

============================== MODEL =================================

interpretation( 4, [number=2331, seconds=0], [

        function(*(_,_), [
                           1, 2, 3, 3,
                           2, 3, 3, 3,
                           3, 3, 3, 3,
                           3, 3, 3, 3 ])
]).

============================== end of model ==========================

============================== STATISTICS ============================

For domain size 4.

Current CPU time: 0.00 seconds (total CPU time: 0.11 seconds).
Ground clauses: seen=64, kept=64.
Selections=2132, assignments=8520, propagations=6194, current_models=2331.
Rewrite_terms=210696, rewrite_bools=65151, indexes=11452.
Rules_from_neg_clauses=586, cross_offs=3767.

============================== end of statistics =====================

User_CPU=0.11, System_CPU=0.26, Wall_clock=0.

Exiting with 2331 models.

Как вы можете видеть, это очень быстро.

Библиотека содержит много других инструментов, таких как isofilter, которая позволяет фильтровать изоморфные варианты алгебры и т.д.