C++ Algorithms: next_permutation()


template
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
if (first == last) return false; //空范围
BidirectionalIterator i = first;
++i;
if (i == last) return false; //只有一个元素
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i--; //相邻元素
if (*i <*ii) { //如果前一个小
BidirectionalIterator j = last;
while (!(*i <*--j)); //从末尾找,直到遇上比*i大的元素
iter_swap(i, j); //交换
reverse(ii, last); //重排
return true;
}
if (i == first) { //进行最前面了
reverse(first, last);
return false;
}
}
}

/* Once iterators i and ii have been properly located, there are still a few more steps left. The next step is to again start searching from the end of the sequence for the first member that is greater than or equal to the member pointed to by i. Because of the previous search for i and ii, we know that at worst the search will end at ii, but it might end earlier. Once this member is located, it is pointed to by iterator j.

Once these three iterators are located, there are only two more simple steps. First, a call is made to iter_swap( i, j ). This simply swaps the members pointed to by i and j. Finally, a call is made to reverse( ii, last ). This has the effect of reversing the sequence that starts at ii and ends at the end of the sequence. */

Reference: "http://marknelson.us/2002/03/01/next-permutation"