नियमों के एक सेट से मेल खाने वाले सभी क्रमपरिवर्तनों को ढूंढना

Question

मुझे एन संख्याएं दी गई हैं और उनके लिए उनके आदेश के बारे में एम नियम लागू हैं। नियमों को इंडेक्स के एक जोड़े में दर्शाया गया है और प्रत्येक जोड़ी (ए, बी) बता रही है कि इंडेक्स ए (ए-वें नंबर) वाला नंबर बी-वें नंबर के बाद होना चाहिए - उसे उसके आगे नहीं होना चाहिए ।

Ex: N = 4 
    1 2 3 4 
    M = 2 
    3 2 
    3 1 

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:) 

एल्गोरिथ्म मुझे सभी क्रमपरिवर्तन उपलब्ध है कि नियमों को तोड़ने नहीं है, उदाहरण की तरह देना चाहिए - 3 हमेशा होना चाहिए 2 के बाद और बाद 1.

मैं bruteforcing की कोशिश की लेकिन यह नहीं था ' टी काम (हालांकि ब्रूटफोर्स को यहां काम करना चाहिए, एन श्रेणी में है (1,8)।)

कोई विचार?

Answer 1

बस एक संकेत के रूप में।

आप अपने नियमों के सेट को ग्राफ के रूप में देख सकते हैं। प्रत्येक सूचकांक एक कशेरुका है, प्रत्येक नियम एक निर्देशित किनारा है।

किसी भी संख्या का सही क्रम (अर्थात एक क्रमचय है कि नियमों को संतुष्ट करता है) तो topological ordering ऊपर ग्राफ के कहा जाता है से मेल खाती है। उत्पन्न करने के लिए सभी अपनी संख्याओं के वैध क्रम आपको उस ग्राफ के सभी संभावित स्थलीय आदेश उत्पन्न करने की आवश्यकता है।

पीएस लिंक किए गए विकिपीडिया पेज पर दिए गए स्थलीय आदेश के लिए पहला एल्गोरिदम पहले से ही एक सरल सीधा समाधान की अनुमति देता है जो सभी वैध क्रमिकताओं को गिनती करेगा। यह कुछ प्रयास करेगा और कुछ देखभाल करने की देखभाल करेगा, लेकिन यह रॉकेट विज्ञान नहीं है।

Answer 2

ब्रूट going through every permutation होगा, जो हे है (एन!), और प्रत्येक क्रमचय के लिए बस पुष्टि करते हैं कि वे aplpy, जो हे (एम) है हर नियम के माध्यम से पाशन मजबूर। यह ओ (एन! एम) समाप्त होता है जो कि हास्यास्पद है, लेकिन इसे ऐसे छोटे सेट के लिए "काम नहीं करना चाहिए"।

Answer 3

ईमानदारी से, आपकी सबसे अच्छी शर्त वापस जाना है और ब्रूट फोर्स समाधान काम करना है। एक बार ऐसा करने के बाद (और यदि आपके पास अभी भी समय है, आदि) तो आप बेहतर एल्गोरिदम खोज सकते हैं।

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

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