random_subset.hpp

#ifndef PASTELSYS_RANDOM_SUBSET_HPP
#define PASTELSYS_RANDOM_SUBSET_HPP

#include "pastel/sys/sequence/random_subset.h"
#include "pastel/sys/random/random_uniform.h"

#include <utility>

namespace Pastel
{

    template <typename RandomAccess_Iterator>
    void randomSubset(
        RandomAccess_Iterator begin,
        RandomAccess_Iterator end,
        integer k)
    {
        integer n = end - begin;

        PENSURE_OP(k, >=, 0);
        PENSURE_OP(k, <=, n);

        if (k == 0 || begin == end)
        {
            return;
        }

        // By the following branching
        // we guarantee that at most n / 2
        // swaps are needed.

        if (2 * k < n)
        {
            // Move to the front those elements which
            // will be in the subset.
            for (integer i = 0;i < k;++i)
            {
                integer index = randomInteger(n - i);

                using std::swap;

                swap(*begin, *(begin + index));

                ++begin;
            }
        }
        else
        {
            // Move to the back those elements which
            // will _not_ be in the subset.
            for (integer i = 0;i < n - k;++i)
            {
                integer index = randomInteger(n - i);

                --end;

                using std::swap;

                swap(*end, *(begin + index));
            }
        }
    }

}

#endif