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

Question

Количество бинарных операций на множестве из 2 элементов равно 2^(2*2)=16,
Количество ассоциативных бинарных операций на этом наборе составляет всего 8.

Количество бинарных операций на наборе из 3 элементов составляет 3^(3*3)=19683.
Количество ассоциативных бинарных операций на этом наборе составляет всего 113. Как узнать, сколько ассоциативных бинарных операций существует на множестве из n элементов?

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

Answer 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 что позволяет фильтровать изоморфные варианты алгебры и т. д.