 Boost :

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