Listing 4

template<class BidirectionalIterator, class Function, class Size>
Function _permute(BidirectionalIterator first, BidirectionalIterator last, 
                                    Size k, Function f, Size n, Size level)
{
    // Algorithm adapted from Donald Knuth, "The Art of Computer Programming,
    //  vol. 1, p. 45, Method 1". Thanks, Donald.
    for( Size x = 0; x < (n-level); ++x )   // rotate every possible value 
                                          // into this level's slot
    {
        if( (level+1) < k ) 
            // if not at max level, recurse down to twirl higher levels first
            f = _permute(first,last,k,f,n,level+1);
        else
            // we are at highest level, this is a unique permutation
            f(first,last);
        // rotate next element in to this level's position & continue
        rotate(first+level,first+level+1,first+n);
    }
    return f;
}
template<class BidirectionalIterator, class Function, class Size>
Function for_each_permutation(BidirectionalIterator first, 
                            BidirectionalIterator last, Size k, Function fn)
{
    return _permute<BidirectionalIterator,Function,Size>(first, last, 
                                           k, fn, distance(first,last), 0);
}