[boost] Thoughts on partial_random_shuffle

From: Ross MacGregor (ross__macgregor_at_[hidden])
Date: 2003-10-09 18:27:35

I have discovered a fundamental mutating algorithm that I think should 
be a standard STL algorithm. It is somewhat tricky to implement (not on 
the order of partial_sort, I'd admit) and complements the other existing 
algorithms.

It is partial_random_shuffle(). It is an optimization of 
random_shuffle() if you would like a subset of random elements from a 
container.

It would have a similar interface to partial_sort() and in many ways 
performs the inverse operation.

sort          (beg, end, op)                      // sorts a container
random_shuffle(beg, end, op)                      // unsorts a container
partial_sort          (beg, sort_end, end, op)    // sorts N elements
partial_random_shuffle(beg, shuffle_end, end, op) // unsorts N elements

I suppose for many applications performing a random_shuffle() on the 
entire container may be acceptable, but I like to use optimized 
algorithms where-ever possible.

Is there any interest in seeing this as a boost algoritm?

Here is my implementation:
--------------------------

#ifndef BOOST_PARTIAL_RANDOM_SHUFFLE_HPP_INCLUDED
#define BOOST_PARTIAL_RANDOM_SHUFFLE_HPP_INCLUDED

#include <cstdlib>

namespace boost {

//  This is a variation of the random_shuffle algorithm
//  that allows you to partially shuffle an STL container.
//  Elements from the sub-range ("p" to "shuffle_end") will
//  be swapped with random elements from the entire range
//  ("p" to "end").
//
//  Usage:
//    // We have 1000 things to index
//    vector<int> indices;
//    for(int i=0; i<1000; i++) indices.push_back(i);
//    // select 100 random indices
//    partial_random_shuffle(indices.begin(), indices.begin() + 100, 
indices.end());
//    indices.resize(100);

//  Contributed by Ross MacGregor

template<class RandomAccessIter>
inline void
partial_random_shuffle(
         RandomAccessIter p,
         RandomAccessIter shuffle_end,
         RandomAccessIter end)
{
     // find number of elements to the end
     size_t range = std::distance(p, end);

     // check for empty range
     if( range != 0 )
     {
         // unable to swap last element
         if( shuffle_end == end )
             --shuffle_end;

         // must have more than 1 element
         // for swap operation to work
         if( --range )
         {
             while( p != shuffle_end )
             {
                 size_t n( rand() % range );

                 std::swap(*p,*(p + n));

                 --range;
                 ++p;
             }
         }
     }
}

template<class RandomAccessIter, class RandomNumberGenerator>
inline void
partial_random_shuffle(
         RandomAccessIter p,
         RandomAccessIter shuffle_end,
         RandomAccessIter end,
         RandomNumberGenerator & rand_func)
{
     // find number of elements to the end
     size_t range = std::distance(p, end);

     // check for empty range
     if( range != 0 )
     {
         // unable to swap last element
         if( shuffle_end == end )
             --shuffle_end;

         // must have more than 1 element
         // for swap operation to work
         if( --range )
         {
             while( p != shuffle_end )
             {
                 size_t n( rand_func(range) );

                 std::swap(*p,*(p + n));

                 --range;
                 ++p;
             }
         }
     }
}

} // namespace boost

#endif  // BOOST_PARTIAL_RANDOM_SHUFFLE_HPP_INCLUDED