Làm thế nào để có được tất cả các hoạt động liên kết đại số trên một tập hợp hữu hạn bằng thuật toán hiệu quả?

Question

Số phép toán nhị phân trên một tập hợp gồm 2 phần tử là 2^(2*2)=16.
Số hoạt động nhị phân kết hợp trên bộ mà chỉ là 8.

Số phép toán hai ngôi trên một tập hợp của 3 yếu tố là 3^(3 * 3) = 19683.
Số hoạt động nhị phân kết hợp trên bộ mà chỉ có 113. là Làm thế nào để biết có bao nhiêu kết hợp nhị phân hoạt động có trên một tập hợp của các yếu tố n?

Ngoài ra để có được tất cả điều này 113 hoạt động và viết vào tập tin, nó là cần thiết để viết một chương trình.
nếu tôi sẽ cố gắng nhận tất cả các hoạt động 19683 và sau đó kiểm tra thuộc tính liên kết "a * (b c) == (a b) * c" cho tất cả các hoạt động 19683, điều này sẽ hoạt động thời gian dài cho n = 4 yếu tố!
Làm cách nào để viết một thuật toán hiệu quả để giải quyết tác vụ này?
Xin hãy giúp tôi!

Answer 1

Hơn đặt ra thuật toán riêng của bạn, đây là một nhiệm vụ cho một công cụ tìm mô hình toán học. Đối với tác vụ này, tôi đặc biệt khuyên bạn nên mace4, một phần của the LADR library. Nó được điều chỉnh đặc biệt cho các vấn đề đại số như thế này. Các đầu vào (chúng ta hãy đặt tên cho nó semigroups.in) sẽ như thế nào:

formulas(sos). 
    (x * y) * z = x * (y * z). 
end_of_list. 

Và sau đó chạy nó bằng cách mace4 -n 4 -N 4 -m 10000 <semigroup.in (tìm tất cả các mô hình 4 phần tử và in lên đến 10.000 trong số họ) tạo ra một đầu ra dài như

... 

============================== 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. 

Như bạn có thể thấy, nó là rất nhanh.

Thư viện chứa nhiều công cụ khác, chẳng hạn như isofilter cho phép bạn lọc các biến thể đẳng cấu của một