एल्गोरिथ्म: कैसे अगले lexicographic क्रमपरिवर्तन खोजने के लिए

यदि आप संक्षेप में बताएंगे कि लेक्सिकोग्राफिक ऑर्डर क्या है, तो यह वर्णमाला क्रम में छंटनी है। यानी वर्णों का क्रम - AAA → AAB → AAC → AAD → ……… → WWW - को वर्णमाला (या हमारे मामले में लेक्सिकोग्राफिक) क्रम में क्रमबद्ध किया जाता है।

कल्पना कीजिए कि आपके पास वर्णों का एक सीमित क्रम है, उदाहरण के लिए, 0, 1, 2, 5, 3, 3, 0 और आपको इन पात्रों के सभी संभावित क्रमों को खोजने की आवश्यकता है। सबसे सहज, लेकिन सबसे कठिन भी, पुनरावर्ती एल्गोरिथ्म है, जब हम अनुक्रम से पहले चरित्र का चयन करते हैं, तो दूसरे, तीसरे, आदि का पुनरावर्ती रूप से चयन करते हैं, जब तक कि अनुक्रम से सभी वर्णों का चयन नहीं किया जाता है। यह स्पष्ट है कि इस तरह के एक एल्गोरिथ्म की जटिलता हे (एन!) है।

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

जिस तरह अगले पूर्णांक मान की गणना करते समय, हमें अनुक्रम के दाईं ओर को बढ़ाने और बाईं ओर को अपरिवर्तित छोड़ने का प्रयास करना चाहिए।

एक उदाहरण के रूप में, उपरोक्त अनुक्रम - (0, 1, 2, 5, 3, 3, 0) लें। अनुक्रम को मूल से अधिक प्राप्त करने के लिए, पहले और दूसरे तत्वों को फिर से व्यवस्थित करना पर्याप्त है, लेकिन यह आवश्यक नहीं है, क्योंकि आप दूसरे और तीसरे तत्वों को पुनर्व्यवस्थित कर सकते हैं और एक क्रम प्राप्त कर सकते हैं जो आरोही क्रम में करीब है। जो हमें अगले नजदीकी क्रमपरिवर्तन आदि की ओर ले जाएगा।

इस मामले में सबसे इष्टतम एल्गोरिथ्म निम्नलिखित होगा:

1. सबसे पहले, आपको सबसे बड़ा गैर-बढ़ती प्रत्यय खोजने की आवश्यकता है। उपरोक्त उदाहरण में, यह होगा - (5, 3, 3, 0)। यदि आप इस क्रम में कोई क्रमपरिवर्तन करने का प्रयास करते हैं, तो यह मूल एक से अधिक नहीं होगा।
   यह कहने योग्य है कि आप इस अनुक्रम को O (n) समय में बाएं से दाएं क्रम से देख सकते हैं।
2. प्रत्यय से अगला तत्व धुरी बिंदु है। हमारे मामले में, यह है 2. धुरी बिंदु हमेशा प्रत्यय के पहले तत्व से कम होगा। इसका मतलब यह है कि प्रत्यय में निश्चित रूप से धुरी बिंदु से अधिक एक तत्व होगा और अगर हम धुरी बिंदु को धुरी बिंदु समर्थन तत्व से अधिक करने वाले प्रत्यय से सबसे छोटे तत्व में बदलते हैं - तो हमें मूल एक से अधिक एक अनुक्रम मिलेगा - हमारे मामले में यह होगा (0, 1, 3, 5) , 3, 2, 0)।
   यानी इस ऑपरेशन का परिणाम न्यूनतम संभव आरोही उपसर्ग होगा।
   
3. और अंतिम चरण में, हमें प्रत्यय को आरोही क्रम में क्रमबद्ध करना होगा। यानी हमें सबसे छोटा संभव प्रत्यय मिलता है। हमारे उदाहरण में, यह (0, 2, 3, 5) होगा और पूरा क्रम (0, 1, 3, 0, 2, 3, 5) जैसा दिखेगा।
   

यह मान अगली lexicographic पुनर्व्यवस्था होगी।



एल्गोरिथ्म के व्यावहारिक अनुप्रयोग के रूप में, अपने काम के सभी समय के लिए मुझे इसकी कभी आवश्यकता नहीं थी, लेकिन उबेर के साथ एक साक्षात्कार के लिए उन्होंने अन्यथा सोचा था :))

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

PYXRU और 646f67 के लिए कई धन्यवाद मुझे एल्गोरिथ्म के एक संभावित अनुकूलन में नाक के साथ प्रहार करने के लिए - बस रिवर्स प्रत्यय करके रैखिक जटिलता के लिए क्रमचय की गणना करने के लिए।

func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }