कुशल एल्गोरिदम द्वारा एक सीमित सेट पर सभी बीजगणितीय सहयोगी संचालन कैसे प्राप्त करें?

2 तत्वों के सेट पर बाइनरी ऑपरेशन की संख्या 2^(2*2)=16 है। enter image description here
कि सेट पर साहचर्य द्विआधारी आपरेशन की संख्या केवल 8.

द्विआधारी आपरेशन के 3 तत्वों का एक सेट पर संख्या 3^(3 * 3) = 19683 है।
उस सेट पर सहयोगी बाइनरी ऑपरेशन की संख्या केवल 113 है। कैसे पता चले कि एन तत्वों के एक सेट पर कितने सहयोगी बाइनरी ऑपरेशन हैं?कुशल एल्गोरिदम द्वारा एक सीमित सेट पर सभी बीजगणितीय सहयोगी संचालन कैसे प्राप्त करें?

यह सभी 113 ऑपरेशन प्राप्त करने और फ़ाइल में लिखने के लिए, एक प्रोग्राम लिखना आवश्यक है।
यदि मैं सभी 1 9 683 परिचालनों को प्राप्त करने का प्रयास करूंगा और फिर इसकी सहयोगी संपत्ति "ए * (बी सी) == ( बी) * सी" सभी 1 9 683 परिचालनों के लिए, यह काम करेगा लेकिन इसे एक लेना चाहिए एन = 4 तत्वों के लिए लंबा समय!
इस कार्य को हल करने के लिए एक कुशल एल्गोरिदम कैसे लिखें?
कृपया मेरी मदद करें!

स्रोत

2014-07-09 IremadzeArchil19910311

आपके प्रश्न के isomorphic वेरिएंट फिल्टर करने के लिए अनुमति देता है व्यापक करने के लिए तरीका है, और शायद यह भी नहीं बहुत अच्छी तरह से इतना के लिए ध्यान केंद्रित शामिल हैं। SO प्रोग्रामिंग के बारे में है और कॉम्बिनेटोरिक्स के बारे में नहीं। –

@JensGustedt यह समस्या combinatorics की तुलना में एल्गोरिदम के बारे में अधिक है। निश्चित रूप से, आपको एल्गोरिदम का विश्लेषण करने के लिए संयोजन की आवश्यकता है (एक निष्पक्ष कार्यान्वयन जटिलता में 'ओ (एन^(एन^2)) जैसे कुछ होगा), लेकिन यह संयोजक के बारे में नहीं है। मैं सहमत हूं कि यह पोस्ट बेहतर अनुकूल हो सकता है [प्रोग्रामर एसई] (http://programmers.stackexchange.com), क्योंकि वे विशेष रूप से [उनके अक्सर पूछे जाने वाले प्रश्न] (http://programmers.stackexchange.com/tour) में एल्गोरिदम का उल्लेख करते हैं। – bheklilr

@bheklilr: ठीक है, तो कम से कम एक [एल्गोरिदम टैग] (http://stackoverflow.com/tags/algorithm/info) (और सार बीजगणित के लिए एक टैग और यहां तक कि एक सेमिग्रुप के लिए भी एक है)। लेकिन मुझे लगता है, यह बहुत व्यापक है, एक अच्छा जवाब शायद बहुत लंबा होगा। आखिरकार, ओपी ने अभी तक कुछ भी नहीं किया है (यह एक "gimme teh algo" प्रश्न है)। IremadzeArchil: शायद http://math.stackexchange.com/? दरअसल, आप पूछ रहे हैं "एन तत्वों के साथ कितने सेमिग्रुप मौजूद हैं?" – mafso

अपने स्वयं के एल्गोरिदम तैयार करने से अधिक, यह गणितीय मॉडल खोजक के लिए एक कार्य है। इस कार्य के लिए, मैं विशेष रूप से mace4 की सिफारिश करता हूं, the LADR library का कौन सा हिस्सा। यह विशेष रूप से इस तरह बीजगणितीय समस्याओं के लिए tuned है। इनपुट (के यह 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-09 20:35:11

'Wall_clock = 0' जाहिर है, ब्रैगिंग एक ऐसी सुविधा है जो मूल रूप से इस लाइब्रेरी द्वारा समर्थित है। उन्होंने वास्तव में सब कुछ के बारे में सोचा था ... –

@ParthianShot यह एक अनुपूरक सुविधा की तरह लगता है। –

कुशल एल्गोरिदम द्वारा एक सीमित सेट पर सभी बीजगणितीय सहयोगी संचालन कैसे प्राप्त करें?

उत्तर

संबंधित मुद्दे