std 中有一个 next_permutation 的算法,见这里,http://en.cppreference.com/w/c…,这个页面上面有一个实现
template<class BidirIt> bool next_permutation(BidirIt first, BidirIt last) { if (first == last) return false; BidirIt i = last; if (first == --i) return false; while (1) { BidirIt i1, i2; i1 = i; if (*--i < *i1) { i2 = last; while (!(*i < *--i2)) ; std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i == first) { std::reverse(first, last); return false; } } }
相关说明在这里,http://fisherlei.blogspot.com/…,但是对着上面的实现看的老费劲,大师写的东西果然晦涩难懂,表达力是强,但是奈何吾辈愚钝啊
遂改写了一个等价的,长这样
template<class BidiIterator> bool next_permutation(BidiIterator first, BidiIterator last) { if (std::distance(first, last) <= 1) { return false; } BidiIterator pivot = last-1; while (1) { pivot--; if (*pivot < *(pivot+1)) { BidiIterator change = last-1; while (*change < *pivot) { change--; } std::iter_swap(pivot, change); std::reverse(pivot+1, last); return true; } if (pivot == first) { std::reverse(first, last); return false; } } }