如何通过高效算法获取有限集合上的所有代数结合运算？

Question

一个由2个元素组成的集合上的二元运算数量为2^(2*2)=16。
在这个集合上可结合的二元运算数量只有8个。

一个由3个元素组成的集合上的二元运算数量为3^(3*3)=19683。
在这个集合上可结合的二元运算数量只有113个。 如何知道n个元素组成的集合上可结合的二元运算具体有多少种？

此外，为了获取所有这113个操作并将其写入文件中，需要编写程序。
如果尝试获取所有19683个操作，然后检查所有19683个操作的可结合属性"a*(bc)==(ab)*c"，这样做虽然可行，但对于n=4元素应该需要很长时间！ 如何编写高效的算法来解决这个任务？ 请帮帮我！

- IremadzeArchil19910311

---

您的问题太泛泛了，而且对于SO来说可能也没有很好的关注点。SO是关于编程的，而不是组合数学。 - Jens Gustedt

@JensGustedt 这个问题更多地涉及算法而非组合数学。当然，您需要应用组合数学来分析算法（一个朴素的实现可能会达到 O(n^(n^2)) 的复杂度），但并不是关于组合数学的。我认为这篇文章可能更适合 程序员SE，因为他们在 他们的FAQ 中明确提到了算法。 - bheklilr

@bheklilr提到StackOverflow至少有一个“algorithm”标签（还有一个抽象代数和半群的标签）。但我认为这个问题太宽泛了，一个好的答案可能会非常长。此外，OP还没有尝试过任何方法（这是一个“gimme teh algo”的问题）。IremadzeArchil建议去math.stackexchange.com。实际上，你在问：“有多少个具有n个元素的半群存在？” - mafso

请查看http://mathoverflow.net/q/110211。 - chepner

你可能会在http://oeis.org/A023814找到一些好的资源。 - bheklilr

请注意，每个关联操作都展现了一种或多种类型的对称性，但非关联操作不会。 - twalberg

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个）会产生类似下面的长输出，涉及IT技术相关内容。

...

============================== 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，可让您过滤代数的同构变体等。

- Petr

---

Wall_clock=0 显然，炫耀是这个库本身支持的一个特性。他们真的想到了一切... - Parthian Shot

@ParthianShot 这似乎更像是一个未实现的功能。 - Petr