Obie funkcje random_sample i random_sample_n pochodzą z rozszerzenia SGI i nie są częścią standardu C++.

Złożoność obu algorytmów jest liniowa.

Funkcje te kopiują elementy z losową kolejnością.

random_sample przeładowywuje dwie funkcje:

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator random_sample(InputIterator first,	InputIterator last,RandomAccessIterator ofirst, RandomAccessIterator olast) 

template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator>
RandomAccessIterator random_sample(InputIterator first, InputIterator last,RandomAccessIterator ofirst, RandomAccessIterator olast, RandomNumberGenerator& rand)

Losowo kopiuje n elementów z zakresu [first, last) do zakresu [ofirst, olast), gdzie n = min(last-first, olast-ofirst). Każdy element ze zbioru wejściowego może pojawić się tylko raz w zbiorze wyjściowym, elementy są wybierane z jednakowym prawdopodobieństwem. Elementy na wyjściu mogą pojawić się w dowolnej kolejności. Pierwsza wersja random_sample korzysta z wewnętrznego generatora liczb losowych, druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez użytkownika generatora. Elementem zwracanym przez random_sample jest element ofirst+n.

• InputIterator - iterator który może być inkrementowany by uzyskać dostęp do następnego obiektu
• RandomAccessIterator - iterator który może być inkrementowany i dekrementownay (kroki mogą być różnej długości)
• RandomNumberGenerator - obiekt-funkcja, który pozwala na genrowanie liczb całkowitych z zakresu [0, N) np.: jeżeli f jest Random Number Generator to f(N) zwraca liczbę całkowitą mniejszą N i wiekszą lub równą zero

random_sample_n przładowywuje dwie funkcje:

template <class ForwardIterator, class OutputIterator, class Distance>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n)

template <class ForwardIterator, class OutputIterator, class Distance, class RandomNumberGenerator>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out,	Distance n, RandomNumberGenerator& rand)

Losowo kopiuje m elementów z zakresu [first, last) do zakresu [out, out+m), gdzie m = min(last-first, n). Każdy element wejściowy może pojawić się na wyjściu dokładnie raz, elementy wybierane są z jednakowym prawdopodobieństwem. Elementy na wyjściu są losowe ale zachowują porządek tak jak były ustawione na wejściu. Pierwsza wersja random_sample_n korzysta z wewnętrznego generatora liczb losowych, druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez użytkownika generatora. Funkcja zwraca element out+m.

• ForwardIterator - iterator który pozwala tylko pobierać następne elementy
• OutputIterator - iterator w którym można zapisać wartość do wskazywanej pozycji i przesunąć się do wskazywania na następny element ale nie można odczytać wartości i cofnąć się
• Distance - wartość całkowita wyznaczająca liczbę elementów na wyjściu
• RandomNumberGenerator - funktor (zachowanie takie samo jak dal random_sample), wartość Distance jest jego argumentem

#include <iostream>
#include <ext/algorithm>
#include <time.h>
#include <vector>
#include <iterator>
 
using namespace std;
 
/*
	Funktor - obiekt który może być wywołany tak jakby był funkcją.
	Obiekt ten definiuje operator().
*/
struct RandomNumberGenerator
{
	int operator()(int r)
	{
		return rand()%r;	
	}
};
 
int main () 
{
	// inicjacja zarodka generatora
	srand(time(NULL));
	int i;
	const int N = 10;
	const int n = 6;
	int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int B[n];
 
	/* random_sample */ 
	cout << "random_sample\n";
	int *ret_val;	                // wskaźnik na wartość zwracaną
	ret_val = __gnu_cxx::random_sample(A, A+N, B, B+n); // przykład działania
	cout << *(ret_val-1) << endl;	// wartość zwrócona
	for(i = 0; i < n; ++i)
		cout << B[i] << " ";	// wartości na wyjściu
	cout << endl;	
 
	RandomNumberGenerator rng;     	                        // funktor 
	cout << rng(13) << endl;		                // przykład użycia funktora
	__gnu_cxx::random_sample(A, A+N, B, B+n, rng);		// wersja z genratorem zewnętrznym 
	copy(B, B + n, ostream_iterator<int>(cout, " "));  	// wypisanie z użyciem operatora ostream_iterator
	cout << endl;										// i funkcji copy
 
	/* random_sample_n */
	cout << "random_sample_n\n";
	vector<int> vec;				    // wektor do zapisu elementów wyjściowych
	vector<int>::const_iterator it;
	insert_iterator<vector<int> > ii(vec, vec.begin()); // insert_iterator do wstawiania elementów do wektora
	__gnu_cxx::random_sample_n(A, A+N, ii, n);          // przykład działania funkcji
	for(it = vec.begin(); it != vec.end(); ++it)
		cout << *it << " ";
	cout << endl;
 
	const int M = 6;
	const int m = 3;
	string AA[] = {"ola", "ala", "ela", "ele", "alo", "olo"}; // przykład działania funkcji na tablicy ze stringami
	// funkcja z generatorem zewnetrznym i wynikiem działania przekazywanym od razu na standardowe wyjście	
	__gnu_cxx::random_sample_n(AA, AA+M, ostream_iterator<string>(cout ," "), m, rng); 
	cout << endl;
 
  return 0;
}

1. http://www.sgi.com/tech/stl/random_sample.html
2. http://www.sgi.com/tech/stl/random_sample_n.html