fork download
copy 
  1. #include <vector>
  2. #include <iterator>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <chrono>
  7.  
  8. template<typename It>
  9. bool next_permutation_bin(It begin, It end)
  10. {
  11.     if (begin == end)
  12.         return false;
  13.  
  14.     It i = begin;
  15.     ++i;
  16.     if (i == end)
  17.         return false;
  18.  
  19.     i = end;
  20.     --i;
  21.  
  22.     while (true)
  23.     {
  24.         It j = i;
  25.         --i;
  26.  
  27.         if (*i < *j)
  28.         {
  29.             auto test = std::lower_bound(std::make_reverse_iterator(end),
  30.                                          std::make_reverse_iterator(i), *i);
  31.  
  32.             std::iter_swap(i, test);
  33.             std::reverse(j, end);
  34.             return true;
  35.         }
  36.  
  37.         if (i == begin)
  38.         {
  39.             std::reverse(begin, end);
  40.             return false;
  41.         }
  42.     }
  43. }
  44.  
  45. template<typename It>
  46. bool next_permutation(It begin, It end)
  47. {
  48.     if (begin == end)
  49.         return false;
  50.  
  51.     It i = begin;
  52.     ++i;
  53.     if (i == end)
  54.         return false;
  55.  
  56.     i = end;
  57.     --i;
  58.  
  59.     while (true)
  60.     {
  61.         It j = i;
  62.         --i;
  63.  
  64.         if (*i < *j)
  65.         {
  66.             It k = end;
  67.  
  68.             while (!(*i < *--k))
  69.                 /* pass */;
  70.  
  71.             iter_swap(i, k);
  72.             reverse(j, end);
  73.             return true;
  74.         }
  75.  
  76.         if (i == begin)
  77.         {
  78.             reverse(begin, end);
  79.             return false;
  80.         }
  81.     }
  82. }
  83.  
  84. int bin_test(int n)
  85. {
  86.     std::vector<int> v(n);
  87.     std::iota(v.begin(), v.end(), 1);
  88.  
  89.     int count = 0;
  90.  
  91.     do
  92.     {
  93.         ++count;
  94.     }
  95.     while (::next_permutation_bin(v.begin(), v.end()));
  96.  
  97.     return count;
  98. }
  99.  
  100. int std_test(int n)
  101. {
  102.     std::vector<int> v(n);
  103.     std::iota(v.begin(), v.end(), 1);
  104.  
  105.     int count = 0;
  106.  
  107.     do
  108.     {
  109.         ++count;
  110.     }
  111.     while (::next_permutation(v.begin(), v.end()));
  112.  
  113.     return count;
  114. }
  115.  
  116. int main() {
  117.  
  118.     int count_bin = 0;
  119.     int count_std = 0;
  120.  
  121.     const auto checkPoint0 = std::chrono::steady_clock::now();
  122.  
  123.     for (std::size_t i = 0; i < 100; i++) {
  124.         count_bin = bin_test(10);
  125.     }
  126.  
  127.     const auto checkPoint1 = std::chrono::steady_clock::now();
  128.     const std::size_t time_bin = std::chrono::duration_cast<std::chrono::milliseconds>(checkPoint1 - checkPoint0).count();
  129.  
  130.     std::cout << "time in milliseconds with binary search : " <<
  131.         time_bin << std::endl;
  132.  
  133.     std::cout << "number of permutations with binary search : " <<
  134.         count_bin << std::endl;
  135.  
  136.     const auto checkPoint2 = std::chrono::steady_clock::now();
  137.  
  138.     for (std::size_t i = 0; i < 100; i++) {
  139.         count_std = std_test(10);
  140.     }
  141.  
  142.     const auto checkPoint3 = std::chrono::steady_clock::now();
  143.     const std::size_t time_std = std::chrono::duration_cast<std::chrono::milliseconds>(checkPoint3 - checkPoint2).count();
  144.  
  145.     std::cout << "time in milliseconds with linear search : " <<
  146.         time_std << std::endl;
  147.  
  148.     std::cout << "number of permutations with linear search : " <<
  149.         count_std << std::endl;
  150.  
  151.     return 0;
  152. }
Success #stdin #stdout 3.59s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
time in milliseconds with binary search : 2270
number of permutations with binary search : 3628800
time in milliseconds with linear search : 1325
number of permutations with linear search : 3628800
https://ideone.com/Pqoc9X
language:
C++ (gcc 8.3)
created:
4 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!