11

2 つの要素のセットに対する 2 項演算の回数は です2^(2*2)=16。 ここに画像の説明を入力
その集合に対する連想バイナリ演算の
ここに画像の説明を入力
数は 8 だけです。3 つの要素の集合に対するバイナリ演算の数は 3^(3*3)=19683 です。
そのセットに対する連想二項演算の数はわずか 113 です。n 個の要素のセットにいくつの連想二項演算があるかを知る方法は?

また、この 113 の操作をすべて取得してファイルに書き込むためには、プログラムを作成する必要があります。
19683 操作すべてを取得してから、19683 操作すべての連想プロパティ "a*(b c)==(a b)*c" をチェックすると、うまくいきますが、n には時間がかかります。 =4つの要素！
このタスクを解決するための効率的なアルゴリズムを作成する方法は?
私を助けてください！

4

1 に答える 1

6

これは、独自のアルゴリズムを考案するだけでなく、数学モデル ファインダーのタスクです。このタスクでは、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は、代数の同型バリアントをフィルタリングできるツールなど、他にも多くのツールが含まれています。

于 2014-07-09T20:35:11.737 に答える