fork download
copy 
  1. #include <iostream>
  2. #include <random>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <vector>
  6.  
  7. using namespace std;
  8. using U = uint_fast32_t;
  9. using VU = vector<U>;
  10. using ULA = uint_fast64_t;
  11.  
  12. enum {
  13.     kLookaheadSize = 64,
  14. };
  15.  
  16. bool cycleRO(const VU& permutation, size_t i_start, size_t& cnt)
  17. {
  18.     if (i_start == 0)
  19.         return true;
  20.  
  21.     auto index = i_start;
  22.     do {
  23.         index = permutation[index];
  24.         ++cnt;
  25.  
  26.         if (index < i_start)
  27.             return false;
  28.  
  29.     } while (index != i_start);
  30.  
  31.     return true;
  32. }
  33.  
  34. void cycleRW(VU& permutation, size_t i_start, ULA& lookahead)
  35. {
  36.     auto index = i_start;
  37.     auto next_ind = permutation[index];
  38.  
  39.     do {
  40.         const auto value = permutation[next_ind];
  41.         permutation[next_ind] = index;
  42.         index = next_ind;
  43.         next_ind = value;
  44.         const auto lookahead_pos = index - i_start;
  45.  
  46.         if (lookahead_pos < kLookaheadSize)
  47.             lookahead |= 1ull << lookahead_pos;
  48.  
  49.     } while (index != i_start);
  50. }
  51.  
  52. size_t invert(VU& permutation)
  53. {
  54.     size_t cnt = 0;
  55.     const auto n = permutation.size();
  56.     ULA lookahead = 0;
  57.  
  58.     for (size_t i_start = 0; i_start != n - 1; ++i_start)
  59.     {
  60.         lookahead >>= 1;
  61.  
  62.         if (!(lookahead&1) && cycleRO(permutation, i_start, cnt))
  63.             cycleRW(permutation, i_start, lookahead);
  64.     }
  65.  
  66.     return cnt;
  67. }
  68.  
  69. int main()
  70. {
  71.     random_device rd;
  72.     mt19937_64 rng(rd());
  73.  
  74.     for (size_t exp = 0; exp <= 20; ++exp)
  75.     {
  76.         const auto n = 1ull << exp;
  77.         VU permutation(n);
  78.         iota(begin(permutation), end(permutation), 0);
  79.         shuffle(begin(permutation), end(permutation), rng);
  80.         VU second_copy(permutation);
  81.         const auto cnt = invert(permutation);
  82.         cout << exp << ' ' << (double)cnt / n << '\n';
  83.  
  84.         invert(permutation);
  85.         if (permutation != second_copy)
  86.         {
  87.             cout << "Wrong result\n";
  88.             return 0;
  89.         }
  90.     }
  91. }
  92.  
Success #stdin #stdout 1.94s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
1 0
2 0.5
3 0.125
4 0.1875
5 0.625
6 0.453125
7 1.00781
8 2.04688
9 2.21094
10 3.01074
11 3.84424
12 4.31763
13 5.27905
14 6.5061
15 6.66675
16 7.53484
17 8.41424
18 8.8167
19 9.07404
20 10.414
https://ideone.com/blO4u0
language:
C++14 (gcc 8.3)
created:
9 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!