#include <iostream>
#include <memory>
#include <numeric>
#include <random>
#include <unordered_map>

int main() {
  constexpr std::size_t min = 1000;
  constexpr std::size_t max = 9999;
  constexpr std::size_t size = 10;
  static_assert(max - min > size, "");

  // Create a new mersenne twister PRNG and seed it with a random 32bit value.
  std::random_device device;
  std::mt19937 engine{device()};

  // Allocate an array on the heap large enough for our output and fill it with
  // the range [min ..  min + size).
  std::unique_ptr<std::size_t[]> array{new std::size_t[size]};
  std::iota(array.get(), array.get() + size, min);

  // Create a new empty hashtable mapping size_t to size_t and ask the hashtable
  // to resize itself it accomidate the maximum number of elements we will be
  // inserting. The reserve is only an optimization that can be commented out.
  std::unordered_map<std::size_t, std::size_t> map;
  map.reserve(max - min - size + 1);

  // We use the above array and hashtable to represent a sparse sequence of all
  // the values in the range [0 .. max-min]. Indexes [0 .. size) are stored in
  // the array and [size .. max-min] are stored in the hashtable and lazily
  // initialized.

  for (std::size_t i = 0; i != size; ++i) {
    // Create a new uniform distribution for the range [i, max - min] and ask it
    // to generate a single number using our PRNG.
    std::uniform_int_distribution<std::size_t> dist{i, max - min};
    auto index = dist(engine);

    // std::swap(array[i], index < size
    //                        ? array[index]
    //                        : map.insert({index, min + index}).first->second);
    // I've broken this statement into several lines to better explain.

    // Pointer to the element we will be swapping with.
    std::size_t *target;

    // Check if the index is in the array or the the hashtable
    if (index < size) {
      // The index is in the array.
      // Save the pointer to the value stored in the array at this index.
      target = &array[index];
    } else {
      // The index is in the hashtable.
      // If the key index does not exist yet, then insert value min + index for
      // this index. If the key already exists then this does no modifications.
      // The result of this operation is a pair of {iterator, bool} where bool
      // tells us if the insert was successful or it already existed, but we
      // dont care about this. The iterator points to the {key, value} pair that
      // is stored in the hashtable after the insert.
      auto pair = map.insert({index, min + index});
      // Save the pointer to the value stored in the hashtable at this index.
      target = &pair.first->second;
    }

    // Swap the ith element of the array with the target element.
    std::swap(array[i], *target);
  }

  // Print the array separated by commas.
  if (size != 0) {
    std::cout << array[0];
    for (size_t i = 1; i != size; ++i) std::cout << ", " << array[i];
    std::cout << "\n";
  }
}