Permutations of a string containing duplicates (C++ Version)

Update: This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See: Recursively printing all permutations of a string containing duplicate characters.

Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not).

int dup_permute(char *str, size_t length) {
    int count = 0;
    std::sort(str, str+length);
    do {
        ++count;
        cout <<  str << '\n';
    }
    while(std::next_permutation(str, str+length));
    return count;
}


Of course, since the major work of this function is being done in the C++ standard library, an explanation of the standard library functions is in order.
First up is the std::sort function. Located in the <algorithm> header, true to its name, it sorts the given range of elements (in this case the string, specified by pointers to its first and last elements). std::next_permutation is a tough one to deal with. The working of this function is too convoluted to explain in a couple of sentences, so, I would recommend you look up this reference and this MSDN article. In short, next_permutation generates the next lexicographically ordered permutation of the given elements using no more than a constant amount of extra space. All that work is done using comparison, swapping and reversing a subset of elements in the array itself. Also, since there is no copying involved, this function is blazing fast. So, the next time someone asks for all permutations of a string, forget about recursion and look at this iterative version. Not only is it correct for the distinct elements case, it works even when the string does contain duplicates. If you liked it, don't forget to leave a comment.