Algorithms: next_permutation()

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;
        }
    }
}

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. :)

This entry was posted in Development and tagged , . Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use basic HTML formatting tags