Interview Question: Next Permutation Array C++
Company Interviews Using C++ Data Structures and Algorithms
#include <bits/stdc++.h>
vector<int> nextPermutation(vector<int> &permutation, int n)
{
int k, l;
for (k = n - 2; k >= 0; k--) {
if (permutation[k] < permutation[k + 1]) {
break;
}
}
if (k < 0) {
reverse(permutation.begin(), permutation.end());
} else {
for (l = n - 1; l > k; l--) {
if (permutation[l] > permutation[k]) {
break;
}
}
swap(permutation[k], permutation[l]);
reverse(permutation.begin()+k+1, permutation.end());
}
return permutation;
}English :
This C++ code defines a function called `nextPermutation` that takes a vector of integers (`permutation`) and an integer `n` as its parameters. The purpose of this function is to find the next lexicographically greater permutation of the elements in the input vector. In other words, it rearranges the elements in the vector to generate the next permutation in lexicographic order, if one exists.
Here’s a step-by-step explanation of how the function works:
1. The function starts by initializing two variables, `k` and `l`. `k` will be used to find the first position in the vector where the elements are in non-decreasing order from right to left, and `l` will be used to find the first position to the right of `k` where an element is greater than the element at position `k`.
2. It then enters a loop that searches for the value of `k`. Starting from the second-to-last element (index `n — 2`) and moving towards the beginning of the vector, it checks if `permutation[k]` is less than `permutation[k + 1]`. If it finds such a position, it breaks out of the loop with the value of `k` set to that position. This is done to identify the rightmost element that can be modified to create a greater permutation.
3. If `k` is less than zero after the loop, it means that the input permutation is already the largest possible lexicographic permutation. In this case, the code reverses the entire vector using the `reverse` function.
4. If `k` is not less than zero, it means a valid `k` position was found, and the code proceeds to find a suitable value for `l`. It starts from the end of the vector (index `n — 1`) and moves towards the left to find the rightmost element greater than the element at position `k`. Once it finds such a position, it breaks out of the loop with the value of `l` set to that position.
5. The code then swaps the elements at positions `k` and `l` in the vector using the `swap` function. This swap ensures that the next permutation will be lexicographically greater.
6. Finally, the code reverses the subvector of `permutation` starting from index `k + 1` to the end of the vector using the `reverse` function. This step ensures that the elements to the right of `k` are in non-decreasing order, creating the smallest lexicographically greater permutation.
7. The function returns the modified `permutation` vector, which now contains the next lexicographically greater permutation.
In summary, this code is used to generate the next lexicographically greater permutation of a given vector of integers. It follows the C++ Standard Library functions `reverse` and `swap` to efficiently achieve this goal.
यह सी++ कोड एक फ़ंक्शन `nextPermutation` को परिभाषित करता है जिसमें एक पूर्णांकों के एक वेक्टर (`permutation`) और एक पूर्णांक `n` दोनों को पैरामीटर के रूप में लेता है। इस फ़ंक्शन का उद्देश्य इनपुट वेक्टर में तत्वों के अगले लेक्सिकोग्राफिक बढ़ते आदान-प्रदान को ढूंढना है। दूसरे शब्दों में, यह वेक्टर के तत्वों को पुनर्व्यवस्थित करके लेक्सिकोग्राफिक क्रम में अगले आदान-प्रदान को उत्पन्न करता है, यदि एक होता है।
यहां फ़ंक्शन काम करने की कदम-से-कदम व्याख्या है:
1. फ़ंक्शन `k` और `l` दो चरों को प्रारंभ करके शुरू होता है। `k` का उपयोग वेक्टर में पहले स्थान को खोजने के लिए किया जाएगा, जहाँ से दाहिने से बाएं ओर तत्व गैर-घटते क्रम में हैं, और `l` का उपयोग `k` स्थान के दाईं ओर ऐसे स्थान को खोजने के लिए किया जाएगा जहाँ `k` स्थान पर बने तत्व से अधिक हैं।
2. यह फ़ंक्शन `k` के मूल्य की खोज के लिए एक लूप में प्रवेश करता है। `n — 2` इंडेक्स से शुरू होकर वेक्टर की शुरुआत की ओर बढ़ते हुए, यह जांचता है कि क्या `permutation[k]` `permutation[k + 1]` से कम है। अगर ऐसा स्थान मिलता है, तो यह उस स्थान पर `k` का मूल्य सेट करके लूप से बाहर निकलता है। इसका उद्देश्य उन तत्वों को पहचानना है जिन्हें बढ़ाने के लिए संशोधित किया जा सकता है, जिनका सबसे अधिक दाहिना मूल्य हो।
3. यदि लूप के बाद `k` जीरो से कम होता है, तो इसका मतलब है कि इनपुट पूर्णांक पहले से ही सबसे बड़ा संभाव्य लेक्सिकोग्राफिक आदान-प्रदान है। इस मामले में, कोड `reverse` फ़ंक्शन का उपयोग करके पूरे वेक्टर को उलट देता है।
4. अगर `k` जीरो से कम नहीं है, तो इसका मतलब है कि एक मान्य `k` स्थान मिला है, और कोड `l` के लिए एक उपयुक्त मूल्य खोजने के लिए आगे बढ़ता है। यह वेक्टर के अंत से (इंडेक्स `n — 1`) शुरू होकर बाईं ओर बढ़ता है ताकि `k` स्थान पर बने तत्व से अधिक तत्व मिल सकें। ऐसा स्थान म
िलते ही, यह उस स्थान पर `l` का मूल्य सेट करके लूप से बाहर निकलता है।
5. इसके बाद, कोड `swap` फ़ंक्शन का उपयोग करके वेक्टर में `k` और `l` स्थानों पर तत्वों का आपस में बदलता है। इस बदलाव से यह सुनिश्चित होता है कि अगला आदान-प्रदान लेक्सिकोग्राफिक रूप से बढ़ा होगा।
6. आखिरकार, कोड `reverse` फ़ंक्शन का उपयोग करके `permutation` के उप-वेक्टर को इंडेक्स `k + 1` से वेक्टर के अंत तक उलट देता है। यह कदम सुनिश्चित करता है कि `k` के दाहिने ओर के तत्व गैर-घटते क्रम में हैं, जिससे सबसे छोटा लेक्सिकोग्राफिक बढ़ता आदान-प्रदान बनता है।
7. फ़ंक्शन संशोधित `permutation` वेक्टर को वापस देता है, जिसमें अब अगला लेक्सिकोग्राफिक बढ़ता आदान-प्रदान है।
संक्षेप में, यह कोड एक दिए गए पूर्णांकों के वेक्टर का अगला लेक्सिकोग्राफिक बढ़ता आदान-प्रदान उत्पन्न करने के लिए उपयोग किया जाता है। इसमें इस उद्देश्य को प्राप्त करने के लिए सी++ मानक पुस्तकालय के फ़ंक्शन `reverse` और `swap` का पालन किया जाता है।यह सी++ कोड एक फ़ंक्शन `nextPermutation` को परिभाषित करता है जिसमें एक पूर्णांकों के एक वेक्टर (`permutation`) और एक पूर्णांक `n` दोनों को पैरामीटर के रूप में लेता है। इस फ़ंक्शन का उद्देश्य इनपुट वेक्टर में तत्वों के अगले लेक्सिकोग्राफिक बढ़ते आदान-प्रदान को ढूंढना है। दूसरे शब्दों में, यह वेक्टर के तत्वों को पुनर्व्यवस्थित करके लेक्सिकोग्राफिक क्रम में अगले आदान-प्रदान को उत्पन्न करता है, यदि एक होता है।
यहां फ़ंक्शन काम करने की कदम-से-कदम व्याख्या है:
1. फ़ंक्शन `k` और `l` दो चरों को प्रारंभ करके शुरू होता है। `k` का उपयोग वेक्टर में पहले स्थान को खोजने के लिए किया जाएगा, जहाँ से दाहिने से बाएं ओर तत्व गैर-घटते क्रम में हैं, और `l` का उपयोग `k` स्थान के दाईं ओर ऐसे स्थान को खोजने के लिए किया जाएगा जहाँ `k` स्थान पर बने तत्व से अधिक हैं।
2. यह फ़ंक्शन `k` के मूल्य की खोज के लिए एक लूप में प्रवेश करता है। `n — 2` इंडेक्स से शुरू होकर वेक्टर की शुरुआत की ओर बढ़ते हुए, यह जांचता है कि क्या `permutation[k]` `permutation[k + 1]` से कम है। अगर ऐसा स्थान मिलता है, तो यह उस स्थान पर `k` का मूल्य सेट करके लूप से बाहर निकलता है। इसका उद्देश्य उन तत्वों को पहचानना है जिन्हें बढ़ाने के लिए संशोधित किया जा सकता है, जिनका सबसे अधिक दाहिना मूल्य हो।
3. यदि लूप के बाद `k` जीरो से कम होता है, तो इसका मतलब है कि इनपुट पूर्णांक पहले से ही सबसे बड़ा संभाव्य लेक्सिकोग्राफिक आदान-प्रदान है। इस मामले में, कोड `reverse` फ़ंक्शन का उपयोग करके पूरे वेक्टर को उलट देता है।
4. अगर `k` जीरो से कम नहीं है, तो इसका मतलब है कि एक मान्य `k` स्थान मिला है, और कोड `l` के लिए एक उपयुक्त मूल्य खोजने के लिए आगे बढ़ता है। यह वेक्टर के अंत से (इंडेक्स `n — 1`) शुरू होकर बाईं ओर बढ़ता है ताकि `k` स्थान पर बने तत्व से अधिक तत्व मिल सकें। ऐसा स्थान म
िलते ही, यह उस स्थान पर `l` का मूल्य सेट करके लूप से बाहर निकलता है।
5. इसके बाद, कोड `swap` फ़ंक्शन का उपयोग करके वेक्टर में `k` और `l` स्थानों पर तत्वों का आपस में बदलता है। इस बदलाव से यह सुनिश्चित होता है कि अगला आदान-प्रदान लेक्सिकोग्राफिक रूप से बढ़ा होगा।
6. आखिरकार, कोड `reverse` फ़ंक्शन का उपयोग करके `permutation` के उप-वेक्टर को इंडेक्स `k + 1` से वेक्टर के अंत तक उलट देता है। यह कदम सुनिश्चित करता है कि `k` के दाहिने ओर के तत्व गैर-घटते क्रम में हैं, जिससे सबसे छोटा लेक्सिकोग्राफिक बढ़ता आदान-प्रदान बनता है।
7. फ़ंक्शन संशोधित `permutation` वेक्टर को वापस देता है, जिसमें अब अगला लेक्सिकोग्राफिक बढ़ता आदान-प्रदान है।
संक्षेप में, यह कोड एक दिए गए पूर्णांकों के वेक्टर का अगला लेक्सिकोग्राफिक बढ़ता आदान-प्रदान उत्पन्न करने के लिए उपयोग किया जाता है। इसमें इस उद्देश्य को प्राप्त करने के लिए सी++ मानक पुस्तकालय के फ़ंक्शन `reverse` और `swap` का पालन किया जाता है।
Hinglish :
Is C++ code mein ek `nextPermutation` function define kiya gaya hai jo ek integers ka vector (`permutation`) aur ek integer `n` ko apne parameters ke roop mein le leta hai. Is function ka uddeshya input vector ke tatvon mein agla lexicographically bada permutation dhoondhna hai. Dusre shabdon mein, yeh vector ke tatvon ko ulatkar agle permutation ko lexicographic kram mein banata hai, agar waisa ek hota hai.
Is function ka kaam kaise karta hai, iska kadam-se-kadam vistar yahan diya gaya hai:
1. Function do variables, `k` aur `l`, ko shuruaat karta hai. `k` ka upayog vector mein tatvon ke daaye se baaye tak non-decreasing order meh sthiti ka pehla sthan dhundhne ke liye kiya jayega, aur `l` ka upayog `k` ke right side mein woh pehla sthan dhundhne ke liye kiya jayega jahan ek tatva `k` ke sthan par se bada hota hai.
2. Fir yeh ek loop mein pravesh karta hai jo `k` ke maan ki khoj karta hai. `n — 2` index se shuruaat karte hue aur vector ke shuruaat ki or badhte hue, yeh dekhta hai ki kya `permutation[k]` `permutation[k + 1]` se kam hai. Agar waisa koi sthan mil jata hai, to us sthan par `k` ke maan ko set karke loop se bahar nikalta hai. Iska maksad woh rightmost tatva dhundhna hai jo bada karke agla permutation banaya ja sakta hai.
3. Agar loop ke baad `k` zero se kam hota hai, to iska matlab hai ki input permutation pehle se hi sabse bada lexicographic permutation hai. Is case mein, yeh code `reverse` function ka upayog karke pura vector palat deta hai.
4. Agar `k` zero se kam nahi hai, to iska matlab hai ki ek valid `k` sthan mil gaya hai, aur code `l` ke liye ek uchit maan dhoondhne ke liye aage badhta hai. Vector ke ant se (index `n — 1`) shuruaat karte hue aur baaye ki or badhkar, yeh `k` sthan par ke tatva se bade rightmost tatva ko dhoondhta hai. Aise sthan milte hi, yeh loop se bahar nikalkar `l` ke maan ko us sthan par set karta hai.
5. Fir, code `swap` function ka upayog karke vector ke `k` aur `l` sthan par ke tatvon ko badalta hai. Is swap se yeh assurance hoti hai ki agla permutation lexicographically bada hoga.
6. Ant mein, code `reverse` function ka upayog karke `permutation` ke subvector ko index `k + 1` se vector ke ant tak palat deta hai. Is kadam se yeh assurance hoti hai ki `k` ke daaye ke tatva non-decreasing order mein honge, aur sabse chota lexicographically bada permutation banaya jayega.
7. Function sambhal kar modificed `permutation` vector ko vapas deta hai, jo ab agla lexicographically bada permutation contain karta hai.
Saransh mein, yeh code diye gaye integers ke vector ka agla lexicographically bada permutation banane ke liye istemal hota hai. Isme C++ Standard Library ke functions `reverse` aur `swap` ka prayog is lakshya ko prabhavit tarike se pura karne ke liye hota hai.
