क्या मल्टीसेट के सभी अद्वितीय परिपत्र क्रमपरिवर्तन उत्पन्न करने के लिए कोई एल्गोरिदम है?

Question

कुछ उत्साही प्रोग्रामिंग करते समय मुझे इस समस्या का सामना करना पड़ा। इस प्रकार समस्या व्यक्त किया जा सकता:

एक मल्टीसेट एक के लिए, चलो पी (ए) को निरूपित ए पी (ए) के सभी संभव क्रमपरिवर्तन की सेट स्वाभाविक रूप से संबंध तोड़ना सबसेट कि तुल्यता हैं में विभाजित है कक्षाएं, समानता संबंध "सर्कुलर बदलावों से संबंधित हो सकती हैं।" उत्पन्न करने वाले सभी समकक्ष वर्गों को उत्पन्न करके सभी समकक्ष वर्गों का आकलन करें।

उदाहरण के लिए, मल्टीसेट {0, 1, 1, 2} पर विचार करें। क्रमपरिवर्तन "0112" और "1201" अद्वितीय क्रमपरिवर्तन हैं, लेकिन उत्तरार्द्ध परिपत्र-पूर्व और इसके विपरीत स्थानांतरित करके पाया जा सकता है। वांछित एल्गोरिदम दोनों उत्पन्न नहीं करना चाहिए।

बेशक एक ब्रूट-बल दृष्टिकोण संभव है: केवल परिपत्र उत्पन्न करें - गोलाकार क्रमिकता के बावजूद - किसी भी मल्टीसेट क्रमपरिवर्तन एल्गोरिदम का उपयोग करके, और पिछले परिणामों की तुलना में पाए गए डुप्लिकेशंस को छोड़ दें। हालांकि, यह अभ्यास में अक्षम है। शून्य बहीखाता नहीं होने पर वांछित एल्गोरिदम को न्यूनतम की आवश्यकता होनी चाहिए।

इस समस्या में किसी भी अंतर्दृष्टि की सराहना की जाती है।

Answer 1

Sawada's algorithm

Answer 2

यह थोड़ा इस नीचे से ऊपर के लिए जाने के लिए आसान है:

अगर एक केवल 1 तत्व होता है, पी (ए) भी एक क्रमचय में शामिल है। एक ही काम को देखना आसान है यदि ए में केवल 2 तत्व होते हैं।

अब, मान लीजिए कि आपके पास पहले से सभी पी (ए) एन तत्वों के साथ हैं, और आप एक तत्व जोड़ते हैं। यह पी (ए) में किसी भी क्रमपरिवर्तन में किसी भी स्पॉट में जा सकता है।

मुझे लगता है कि यह विचार आपकी पसंद की भाषा में सीधे एक पुनरावर्ती एल्गोरिदम में अनुवाद करता है, और उम्मीद है कि मेरी व्याख्या पर्याप्त स्पष्ट थी।

संपादित करें: मैं जानता हूँ कि मैं एक तरह से तथ्य यह है कि कोई डुप्लिकेट तत्व शामिल हो सकते, लेकिन अभी भी वह हिस्सा :)

सिर्फ एक यद्यपि के रूप में के बारे में सोच पर ध्यान नहीं दिया - अगर आप क्रमचय एल्गोरिथ्म शुरू करने से पहले एक हल कर, मुझे लगता है यह डुप्लिकेट को खत्म कर सकता है। समस्या मुझे लगता है कि हम इस रूपक का उपयोग कर सकते की एक सहज ज्ञान युक्त समझ के लिए (अभी भी बहुत कि के बारे में सोच)

Answer 3

। दीवार पर एक घड़ी को विज़ुअलाइज़ करें, लेकिन चेहरे पर 12 पदों के बजाय यह एन है जहां एन आपके सेट में तत्वों की संख्या है।

फिर प्रत्येक समकक्ष वर्ग घड़ी के चेहरे पर स्थिति के लिए ए के तत्व का असाइनमेंट है।

एक बार समान समकक्ष वर्ग से एक और क्रमपरिवर्तन आवंटित किया जा सकता है, बस दीवार पर घड़ी को घूर्णन करके उत्पन्न किया जा सकता है।

ए के एक और असंबंधित क्रमपरिवर्तन उत्पन्न करने के लिए आपको कम से कम एक अन्य तत्व पर तत्व छोड़ने की आवश्यकता है।

अब एल्गोरिदम जैसा कि मैं इसे देखता हूं, एक असाइनमेंट के साथ शुरू करना होगा उदाहरण के लिए हमारे पास ए = {ए, बी, सी, डी} में चार तत्व थे और हमने उन्हें 12, 3, 6 और 9 में सौंपा दृश्य स्पष्टता के लिए क्रमशः पदों। फिर हमारा पहला ऑपरेशन ए और बी स्वैप करना होगा। फिर ए और सी, फिर ए और डी, फिर हम बी पर जाएंगे और तत्व को 3 स्थिति में स्वैप करेंगे जो अब सी है।

जब तक हम पहुंचे तो यह करने से सभी समकक्ष वर्गों के प्रतिनिधि उत्पन्न होंगे।

यह डुप्लिकेट की देखभाल नहीं करता है, लेकिन यह कहीं अधिक ए के सभी क्रमपरिवर्तन के उत्पादन की तुलना कुशल होना चाहिए

Answer 4

सोचा कि मेरे दिमाग में स्प्रिंग्स है कि कम से कम एक तत्व है कि किसी भी सेट के लिए है कि केवल एक बार प्रकट होता है तो आप उस तत्व को सभी उत्तरों के लिए अपनी सूची की पहली स्थिति में डाल सकते हैं और फिर शेष संख्याओं के सभी क्रमपरिवर्तन उत्पन्न कर सकते हैं। यह एक बहुत छोटा समाधान है क्योंकि तथ्य यह है कि आपका पहला तत्व अद्वितीय है यह सुनिश्चित करता है कि तत्वों को स्थानांतरित करने के चक्र द्वारा कोई समकक्ष नहीं है। स्पष्ट रूप से आपके द्वारा उत्पन्न सभी समाधान अद्वितीय होना चाहिए।

स्पष्ट समस्या यह है कि यदि आपके पास एकल तत्व नहीं हैं तो यह पूरी तरह से टूट जाता है। मुख्य कारण यह है कि मैंने इसे रखा है क्योंकि डुप्लिकेट से निपटने के कई अन्य समाधान हैं और मुझे लगता है कि यह उनके मुकाबले अधिक प्रभावी है (अधिक मामलों को हल करता है) इसलिए उल्लेख करने योग्य है। यह समझने के मामले में यह भी बहुत सरल है कि यह कैसे काम करता है और इसे कार्यान्वित करता है। मुझे उम्मीद है कि मेरी तर्क ध्वनि है। आगे विचार के लिए ;-)

संपादित करें:

यह मेरे लिए होता है कि इस सिद्धांत को स्थिति है जहाँ आप कुछ हद तक डुप्लिकेट के लिए बढ़ाया जा सकता है।

यदि आप एक तत्व लेते हैं (जिसे हम अब मानते हैं) तो आप केवल इसके क्रमपरिवर्तनों को देख सकते हैं और कौन सा चक्र शिफ्ट पुनरावृत्ति की अनुमति देगा, जैसा कि पहले माना जाता है कि आप सामान्यता के नुकसान के बिना किसी को "लॉक" कर सकते हैं । जैसे अगर आप 6 तत्वों की कुल राशि और एक इस सेट में दो बार दिखाई देता है तो आप कर सकते हैं:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

इनमें से पिछले पहले के समान ही है (भीतर चक्रीय शिफ्ट) तो दूसरे और चौथे स्थान पर, अनदेखा किया जा सकता है। तीसरे (AXXAXX) को अपने आप को वापस पाने के लिए तीन से चक्रवात किया जा सकता है, इसलिए चक्रों की संभावना है। पहले दो चक्रों को कभी भी जन्म नहीं दे सकते हैं इससे कोई फर्क नहीं पड़ता कि आप उन्हें कितनी बार चक्र देते हैं, हालांकि आप केवल शेष तत्वों को वितरित करते हैं जिन्हें आप केवल यह सुनिश्चित करते हैं कि वे अद्वितीय वितरण हैं और आपको चक्र परिणामों से अनूठा होने की गारंटी है।

चक्र (AXXAXX) के तीसरे पैटर्न के लिए आपको तत्व बी को देखने और उन लोगों के लिए प्रक्रिया दोहराने की आवश्यकता होगी। इस बार असुविधाजनक रूप से आप समय बचाने के लिए पहले मूल्य को लॉक करने की चाल का उपयोग करने में असमर्थ होंगे।

मुझे 100% यकीन नहीं है कि आप इसे पूरी तरह से काम करने वाले कार्यक्रम में कैसे बनाने के बारे में जानेंगे, लेकिन इसके कुछ लोग बलपूर्वक बलपूर्वक होने से बचने के तरीके पर हैं।

Answer 5

मैं यहाँ एक समाधान अजगर

import itertools as it 

L = ['a','b','c','d'] 
B = it.combinations(L,2) 
swaplist = [e for e in B] 
print 'List of elements to permute:' 
print swaplist 
print 
unique_necklaces = [] 
unique_necklaces.append(L) 
for pair in swaplist: 
    necklace = list(L) 
    e1 = pair[0] 
    e2 = pair[1] 
    indexe1 = L.index(e1) 
    indexe2 = L.index(e2) 
    #swap 
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1] 
    unique_necklaces.append(necklace) 

for n in unique_necklaces: 
    # Commented code display the rotation of the elements in each necklace 
    print 'Necklaces' 
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)] 

विचार दो तत्वों के क्रमपरिवर्तन द्वारा विभिन्न हार का निर्माण करना है में लागू प्रस्ताव करते हैं।चार तत्वों की एक सूची के लिए ए, बी, सी, डी अलगो उपज:

['a', 'b', 'c', 'd'] 
['b', 'a', 'c', 'd'] 
['c', 'b', 'a', 'd'] 
['d', 'b', 'c', 'a'] 
['a', 'c', 'b', 'd'] 
['a', 'd', 'c', 'b'] 
['a', 'b', 'd', 'c']