====== random_sample i random_sample_n ======

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 =====

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)


== Opis działania ==
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.
	
== Parametry ==
  * 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 =====

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)

== Opis działania ==
	
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.

== Parametry ==
  * 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


===== Przykład =====
<code cpp>
#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;
}
</code>

===== Linki =====
  - http://www.sgi.com/tech/stl/random_sample.html
  - http://www.sgi.com/tech/stl/random_sample_n.html