#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());
}