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

Question

对一组 2 个元素进行二元运算的次数是 2^(2*2)=16。
该集合上的关联二进制操作数仅为 8。

对一组 3 个元素进行二元运算的次数为 3^(3*3)=19683。
该集合上的关联二进制操作数仅为 113。如何知道n个元素的集合有多少个结合二元运算？

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

Answer 1

这不仅仅是设计你自己的算法，这是数学模型发现者的任务。对于此任务，我特别推荐 mace4 , the LADR library 的哪一部分.它专门针对此类代数问题进行了调整。输入(我们将其命名为 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这允许您过滤代数等的同构变体。