C++:
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
–i;
for(;;) {
BidirectionalIterator ii = i–;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*–j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
–i;
for(;;) {
BidirectionalIterator ii = i–;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*–j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
An amazing piece of code! This is the next_permutation() function in the Standard C++ Library, defined in <algorithm>. And the best part… it’s O(n) complexity.
Iterators are a generalization of pointers. That should make it much easier to understand 😀
It checks for the initial conditions of 0 length and 1 character strings, and then iterates through the given string from the last character to find the next largest permutation.
What I wonder is it’s response when we enter Alphanumeric data, or even Mixed Alphabets (Smalls and Caps). That should break it. 🙂