#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 << ' ';
	}
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8dmVjdG9yPgoKbmFtZXNwYWNlCnsKCXN0ZDo6cmFuZG9tX2RldmljZSByZDsKCXN0ZDo6bXQxOTkzNyBlbmd7IHJkKCkgfTsKCXN0ZDo6dW5pZm9ybV9yZWFsX2Rpc3RyaWJ1dGlvbjw+IGRpc3Q7IC8vIFswLDEpCglkb3VibGUgbXlfcmFuZCgpIHsgcmV0dXJuIGRpc3QoZW5nKTsgfQp9CgovLyBQcm9ncmFtbWluZyBQZWFybHMgY29sdW1uIDExLjIKLy8gS251dGgncyBhbGdvcml0aG0gUyAoMy40LjIpCi8vIG91dHB1dCBNIGludGVnZXJzIChpbiBvcmRlcikgaW4gcmFuZ2UgMS4uTgp0ZW1wbGF0ZSA8dHlwZW5hbWUgT3V0SXQ+CnZvaWQga251dGhfcyhpbnQgTSwgaW50IE4sIE91dEl0IGRlc3QpCnsKCWRvdWJsZSBzZWxlY3QgPSBNLCByZW1haW5pbmcgPSBOOwoJZm9yIChpbnQgaSA9IDE7IGkgPD0gTjsgKytpKSB7CgkJaWYgKG15X3JhbmQoKSA8IHNlbGVjdCAvIHJlbWFpbmluZykgewoJCQkqZGVzdCsrID0gaTsKCQkJLS1zZWxlY3Q7CgkJfQoJCS0tcmVtYWluaW5nOwoJfQp9CgppbnQgbWFpbigpCnsKCXN0ZDo6dmVjdG9yPGludD4gZGF0YTsKCglrbnV0aF9zKDIwLCAyMDAsIGJhY2tfaW5zZXJ0ZXIoZGF0YSkpOyAvLyAyMCB2YWx1ZXMgaW4gWzEsMjAwXQoKCWZvciAoYXV0byB2YWx1ZSA6IGRhdGEpIHsKCQlzdGQ6OmNvdXQgPDwgdmFsdWUgPDwgJyAnOwoJfQp9Cg==