对一组 2 个元素进行二元运算的次数是 2^(2*2)=16
。
该集合上的关联二进制操作数仅为 8。
对一组 3 个元素进行二元运算的次数为 3^(3*3)=19683。
该集合上的关联二进制操作数仅为 113。
如何知道n个元素的集合有多少个结合二元运算?
另外为了得到所有这113个操作并写入文件,有必要编写一个程序。
如果我尝试获取所有 19683 操作,然后检查所有 19683 操作的关联属性“a*(bc)==(ab)*c”,这会起作用,但是n=4 个元素应该需要很长时间!
如何编写一个高效的算法来解决这个任务?
请帮助我!
最佳答案
这不仅仅是设计你自己的算法,这是数学模型发现者的任务。对于此任务,我特别推荐 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
这允许您过滤代数等的同构变体。
关于c - 如何通过高效算法得到有限集上的所有代数结合运算?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24659043/