fork download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <numeric>
  4. #include <random>
  5. #include <unordered_map>
  6.  
  7. int main() {
  8.   constexpr std::size_t min = 1000;
  9.   constexpr std::size_t max = 9999;
  10.   constexpr std::size_t size = 10;
  11.   static_assert(max - min > size, "");
  12.  
  13.   // Create a new mersenne twister PRNG and seed it with a random 32bit value.
  14.   std::random_device device;
  15.   std::mt19937 engine{device()};
  16.  
  17.   // Allocate an array on the heap large enough for our output and fill it with
  18.   // the range [min ..  min + size).
  19.   std::unique_ptr<std::size_t[]> array{new std::size_t[size]};
  20.   std::iota(array.get(), array.get() + size, min);
  21.  
  22.   // Create a new empty hashtable mapping size_t to size_t and ask the hashtable
  23.   // to resize itself it accomidate the maximum number of elements we will be
  24.   // inserting. The reserve is only an optimization that can be commented out.
  25.   std::unordered_map<std::size_t, std::size_t> map;
  26.   map.reserve(max - min - size + 1);
  27.  
  28.   // We use the above array and hashtable to represent a sparse sequence of all
  29.   // the values in the range [0 .. max-min]. Indexes [0 .. size) are stored in
  30.   // the array and [size .. max-min] are stored in the hashtable and lazily
  31.   // initialized.
  32.  
  33.   for (std::size_t i = 0; i != size; ++i) {
  34.     // Create a new uniform distribution for the range [i, max - min] and ask it
  35.     // to generate a single number using our PRNG.
  36.     std::uniform_int_distribution<std::size_t> dist{i, max - min};
  37.     auto index = dist(engine);
  38.  
  39.     // std::swap(array[i], index < size
  40.     //                        ? array[index]
  41.     //                        : map.insert({index, min + index}).first->second);
  42.     // I've broken this statement into several lines to better explain.
  43.  
  44.     // Pointer to the element we will be swapping with.
  45.     std::size_t *target;
  46.  
  47.     // Check if the index is in the array or the the hashtable
  48.     if (index < size) {
  49.       // The index is in the array.
  50.       // Save the pointer to the value stored in the array at this index.
  51.       target = &array[index];
  52.     } else {
  53.       // The index is in the hashtable.
  54.       // If the key index does not exist yet, then insert value min + index for
  55.       // this index. If the key already exists then this does no modifications.
  56.       // The result of this operation is a pair of {iterator, bool} where bool
  57.       // tells us if the insert was successful or it already existed, but we
  58.       // dont care about this. The iterator points to the {key, value} pair that
  59.       // is stored in the hashtable after the insert.
  60.       auto pair = map.insert({index, min + index});
  61.       // Save the pointer to the value stored in the hashtable at this index.
  62.       target = &pair.first->second;
  63.     }
  64.  
  65.     // Swap the ith element of the array with the target element.
  66.     std::swap(array[i], *target);
  67.   }
  68.  
  69.   // Print the array separated by commas.
  70.   if (size != 0) {
  71.     std::cout << array[0];
  72.     for (size_t i = 1; i != size; ++i) std::cout << ", " << array[i];
  73.     std::cout << "\n";
  74.   }
  75. }
  76.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2819, 5419, 6816, 2965, 4075, 1315, 7200, 9465, 8409, 4418
https://ideone.com/gmaBri
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!