Boost logo

Boost :

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
+44 1539 561830 Mobile +44 7714 33 02 04
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
|
|


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk