#include <random> // für zufallszahlen und verteilung
#include <algorithm> // für swap (und copy bei der ausgabe)
#include <unordered_set> // für random_sample
#include <iostream> // nur für ausgabe
#include <iterator> // nur für ausgabe
 
// O(k), aber die Werte müssen schon im Speicher sein.
template <typename RandomIt, typename URNG>
void partial_shuffle(RandomIt first, RandomIt mid, RandomIt last, URNG&& g) {
  auto n = last - first;
  auto k = mid - first;
  for (decltype(n) i{}; i < k; ++i) {
    auto j = std::uniform_int_distribution<decltype(i)>(i, n - 1)(g);
    using std::swap;
    swap(first[i], first[j]);
  }
}
 
// O(k) sofern k viel kleiner wie n
template <typename Distribution, typename OutIt, typename URNG>
void random_sample(Distribution&& pool, std::size_t k, OutIt out, URNG g) {
  std::unordered_set<decltype(pool(g))> sample;
  while (sample.size() < k) {
    auto elem = pool(g);
    if (sample.insert(elem).second)
      *out++ = std::move(elem);
  }
}
 
int main()
{
  std::vector<int> v(100);
  std::iota(v.begin(), v.end(), 1);
  partial_shuffle(v.begin(), v.begin()+10, v.end(),
                  std::mt19937());
  std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
 
  std::cout << '\n';
 
  random_sample(std::uniform_int_distribution<int>(1, 100),
                10,
                std::ostream_iterator<int>(std::cout, " "),
                std::mt19937());
}

I2luY2x1ZGUgPHJhbmRvbT4gLy8gZsO8ciB6dWZhbGxzemFobGVuIHVuZCB2ZXJ0ZWlsdW5nCiNpbmNsdWRlIDxhbGdvcml0aG0+IC8vIGbDvHIgc3dhcCAodW5kIGNvcHkgYmVpIGRlciBhdXNnYWJlKQojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4gLy8gZsO8ciByYW5kb21fc2FtcGxlCiNpbmNsdWRlIDxpb3N0cmVhbT4gLy8gbnVyIGbDvHIgYXVzZ2FiZQojaW5jbHVkZSA8aXRlcmF0b3I+IC8vIG51ciBmw7xyIGF1c2dhYmUKCi8vIE8oayksIGFiZXIgZGllIFdlcnRlIG3DvHNzZW4gc2Nob24gaW0gU3BlaWNoZXIgc2Vpbi4KdGVtcGxhdGUgPHR5cGVuYW1lIFJhbmRvbUl0LCB0eXBlbmFtZSBVUk5HPgp2b2lkIHBhcnRpYWxfc2h1ZmZsZShSYW5kb21JdCBmaXJzdCwgUmFuZG9tSXQgbWlkLCBSYW5kb21JdCBsYXN0LCBVUk5HJiYgZykgewogIGF1dG8gbiA9IGxhc3QgLSBmaXJzdDsKICBhdXRvIGsgPSBtaWQgLSBmaXJzdDsKICBmb3IgKGRlY2x0eXBlKG4pIGl7fTsgaSA8IGs7ICsraSkgewogICAgYXV0byBqID0gc3RkOjp1bmlmb3JtX2ludF9kaXN0cmlidXRpb248ZGVjbHR5cGUoaSk+KGksIG4gLSAxKShnKTsKICAgIHVzaW5nIHN0ZDo6c3dhcDsKICAgIHN3YXAoZmlyc3RbaV0sIGZpcnN0W2pdKTsKICB9Cn0KIAovLyBPKGspIHNvZmVybiBrIHZpZWwga2xlaW5lciB3aWUgbgp0ZW1wbGF0ZSA8dHlwZW5hbWUgRGlzdHJpYnV0aW9uLCB0eXBlbmFtZSBPdXRJdCwgdHlwZW5hbWUgVVJORz4Kdm9pZCByYW5kb21fc2FtcGxlKERpc3RyaWJ1dGlvbiYmIHBvb2wsIHN0ZDo6c2l6ZV90IGssIE91dEl0IG91dCwgVVJORyBnKSB7CiAgc3RkOjp1bm9yZGVyZWRfc2V0PGRlY2x0eXBlKHBvb2woZykpPiBzYW1wbGU7CiAgd2hpbGUgKHNhbXBsZS5zaXplKCkgPCBrKSB7CiAgICBhdXRvIGVsZW0gPSBwb29sKGcpOwogICAgaWYgKHNhbXBsZS5pbnNlcnQoZWxlbSkuc2Vjb25kKQogICAgICAqb3V0KysgPSBzdGQ6Om1vdmUoZWxlbSk7CiAgfQp9CiAKaW50IG1haW4oKQp7CiAgc3RkOjp2ZWN0b3I8aW50PiB2KDEwMCk7CiAgc3RkOjppb3RhKHYuYmVnaW4oKSwgdi5lbmQoKSwgMSk7CiAgcGFydGlhbF9zaHVmZmxlKHYuYmVnaW4oKSwgdi5iZWdpbigpKzEwLCB2LmVuZCgpLAogICAgICAgICAgICAgICAgICBzdGQ6Om10MTk5MzcoKSk7CiAgc3RkOjpjb3B5KHYuYmVnaW4oKSwgdi5lbmQoKSwgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPGludD4oc3RkOjpjb3V0LCAiICIpKTsKIAogIHN0ZDo6Y291dCA8PCAnXG4nOwogCiAgcmFuZG9tX3NhbXBsZShzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+KDEsIDEwMCksCiAgICAgICAgICAgICAgICAxMCwKICAgICAgICAgICAgICAgIHN0ZDo6b3N0cmVhbV9pdGVyYXRvcjxpbnQ+KHN0ZDo6Y291dCwgIiAiKSwKICAgICAgICAgICAgICAgIHN0ZDo6bXQxOTkzNygpKTsKfQ==