c - 如何通过高效算法获得有限集合上的所有代数关联运算？

Question

一组 2 个元素的二元运算数是2^(2*2)=16.
该集合上的关联二元运算数仅为 8。

一组 3 个元素的二元运算数为 3^(3*3)=19683。
该集合上的关联二元运算数只有 113。如何知道一组 n 个元素有多少关联二元运算？

此外，为了获得所有这 113 次操作并写入文件，还需要编写一个程序。
如果我将尝试获取所有 19683 操作，然后检查所有 19683 操作的关联属性“a*(b c)==(a b)*c”，这将起作用，但这需要很长时间=4个元素！
如何编写一个高效的算法来解决这个任务？
请帮我！

Answer 1

这不仅仅是设计自己的算法，而是数学模型查找器的任务。对于这项任务，我特别推荐LADR 库的mace4哪个部分。它专门针对这样的代数问题进行了调整。输入（让我们命名）看起来像：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允许您过滤代数的同构变体等。