RE: [boost] Thoughts on partial_random_shuffle

From: Paul A. Bristow (boost_at_[hidden])
Date: 2003-10-12 06:57:54

Looks sensible - but can you give example(s)/references where this would be
useful in practice?

Paul

(Is p == shuffle_begin? Why are there not 4 parameters, thingys begin and end,
and both shuffle_begin and shuffle_end?)

Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB  UK
[phone]   Mobile [phone]
mailto:pbristow_at_[hidden]

| -----Original Message-----
| From: boost-bounces_at_[hidden]
| [mailto:boost-bounces_at_[hidden]]On Behalf Of Ross MacGregor
| Sent: Friday, October 10, 2003 12:28 AM
| To: boost_at_[hidden]
| Subject: [boost] Thoughts on partial_random_shuffle
|
|
|
| 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
|
|
|
| _______________________________________________
| Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
|
|