#include <iostream>
#include <random>
#include <vector>

namespace
{
	std::random_device rd;
	std::mt19937 eng{ rd() };
	std::uniform_real_distribution<> dist; // [0,1)
	double my_rand() { return dist(eng); }
}

// Programming Pearls column 11.2
// Knuth's algorithm S (3.4.2)
// output M integers (in order) in range 1..N
template <typename OutIt>
void knuth_s(int M, int N, OutIt dest)
{
	double select = M, remaining = N;
	for (int i = 1; i <= N; ++i) {
		if (my_rand() < select / remaining) {
			*dest++ = i;
			--select;
		}
		--remaining;
	}
}

int main()
{
	std::vector<int> data;

	knuth_s(20, 200, back_inserter(data)); // 20 values in [1,200]

	for (auto value : data) {
		std::cout << value << ' ';
	}
}