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