Std :: next_permutation Implementation Explanation seems ineffective?

Question

I was curious how std: next_permutation was implemented, so I extracted the gnu libstdC ++ 4.7 version and misinformed the identifiers and formatting to create the next demo ...

#include <vector> #include <iostream> #include <algorithm> using namespace std; template<typename It> bool next_permutation(It begin, It end) { if (begin == end) return false; It i = begin; ++i; if (i == end) return false; i = end; --i; while (true) { It j = i; --i; if (*i < *j) { It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true; } if (i == begin) { reverse(begin, end); return false; } } 

}

  int main() { vector<int> v = { 1, 2, 3, 4 }; do { for (int i = 0; i < 4; i++) { cout << v[i] << " "; } cout << endl; } while (::next_permutation(v.begin(), v.end())); 

}

My question is:

 while (!(*i < *--k)) /* Iterating linearly */; 

Why don't we do a binary search instead of a naive linear iteration, since the sequence from [i + 1, end) is in descending order? This will increase search efficiency. How does the standard function in "algorithm.h" neglect such a thing that leads to increased productivity and efficiency? Pls someone explain ...

Answer 1

You rarely have an array that you want to rearrange with more than 15 elements (or even less), because you need to process 15! > 10 ^ 12 different permutations. And for arrays with such a small size, binary search is less efficient than a simple linear search.