自己实现了一下C++STL中的next_permutation，名为ant_next_permutation，发下代码

//作者: Gods_巨蚁<br />//反馈方式<br />//E-mail:ljsunlin@126.com<br />//QQ:517377100<br />//Blog:http://hi.baidu.com/zhongji<br />//Permutation.h<br />#include <algorithm></p> <p>//与STL库中的next_permutation相比，增加了设置仿函数功能<br />//std::less<typename std::iterator_traits<BidirectionalIterator>::value_type>打算使用默认模板参数，结果仅允许在类模板上使用。。。<br />template<class BidirectionalIterator><br />bool ant_next_permutation(<br /> BidirectionalIterator beg,<br /> BidirectionalIterator end<br /> )<br />{<br /> return ant_next_permutation(beg, end, std::less<typename std::iterator_traits<BidirectionalIterator>::value_type>());<br /> /*<br /> BidirectionalIterator pos1, pos2;<br /> pos1 = end;</p> <p> do{<br /> --pos1;<br /> if(pos1 == beg) //已经全部是降序排列了，重设为升序排列<br /> {<br /> //std::sort(beg, end); 这里不应该用算法sort，否则该函数用于list容器将会出现编译错误<br /> BidirectionalIterator it1 = beg, it2 = end;<br /> --it2;<br /> for(;it1 != it2;)<br /> {<br /> std::iter_swap(it1, it2);<br /> if(++it1 == it2)break;<br /> --it2;<br /> }<br /> return false;<br /> }<br /> pos2 = pos1;<br /> --pos2;<br /> }while(*pos1 < *pos2); //若后者小于前者，继续执行</p> <p> //[pos1, end) 当前是一个降序排列<br /> //pos2此时指向前一个数据，小于降序排列中的最大值<br /> //现在要用降序排列中的大于pos2处数值的最小数替换掉pos2处数值<br /> BidirectionalIterator pos3;<br /> pos3 = end;<br /> --pos3;<br /> for(; *pos3 < *pos2; --pos3); //执行后pos3处数值为需要替换数值 2此处原来是*pos3 <= *pos2，应该设为<比较合适<br /> std::iter_swap(pos3, pos2); //互换<br /> //确定了pos2的新值后，pos2后方pos1位置的降序排列需要更新为升序排列<br /> //std::sort(pos1, end); 这里不应该用算法sort，否则该函数用于list容器将会出现编译错误<br /> BidirectionalIterator it1 = pos1, it2 = end;<br /> --it2;<br /> for(;it1 != it2;)<br /> {<br /> std::iter_swap(it1, it2);<br /> if(++it1 == it2)break;<br /> --it2;<br /> }<br /> return true;<br /> */<br />}</p> <p>template<class BidirectionalIterator, class BinaryPredicate><br />bool ant_next_permutation(<br /> BidirectionalIterator beg,<br /> BidirectionalIterator end,<br /> BinaryPredicate op// = std::less<typename std::iterator_traits<BidirectionalIterator>::value_type>()//这里无法使用该默认参数<br /> )<br />{<br /> BidirectionalIterator pos1, pos2;<br /> pos1 = end;</p> <p> do{<br /> --pos1;<br /> if(pos1 == beg) //已经全部是降序排列了，重设为升序排列<br /> {<br /> //std::sort(beg, end); 这里不应该用算法sort，否则该函数用于list容器将会出现编译错误<br /> BidirectionalIterator it1 = beg, it2 = end;<br /> --it2;<br /> for(;it1 != it2;)<br /> {<br /> std::iter_swap(it1, it2);<br /> if(++it1 == it2)break;<br /> --it2;<br /> }<br /> return false;<br /> }<br /> pos2 = pos1;<br /> --pos2;<br /> }while( op(*pos1, *pos2) ); //若后者小于前者，继续执行</p> <p> //[pos1, end) 当前是一个降序排列<br /> //pos2此时指向前一个数据，小于降序排列中的最大值<br /> //现在要用降序排列中的大于pos2处数值的最小数替换掉pos2处数值<br /> BidirectionalIterator pos3;<br /> pos3 = end;<br /> --pos3;<br /> for(; op(*pos3, *pos2); --pos3); //执行后pos3处数值为需要替换数值<br /> std::iter_swap(pos3, pos2); //互换<br /> //确定了pos2的新值后，pos2后方pos1位置的降序排列需要更新为升序排列<br /> //std::sort(pos1, end); 这里不应该用算法sort，否则该函数用于list容器将会出现编译错误<br /> BidirectionalIterator it1 = pos1, it2 = end;<br /> --it2;<br /> for(;it1 != it2;)<br /> {<br /> std::iter_swap(it1, it2);<br /> if(++it1 == it2)break;<br /> --it2;<br /> }<br /> return true;<br />}</p> <p>template<class BidirectionalIterator><br />bool ant_prev_permutation(<br /> BidirectionalIterator beg,<br /> BidirectionalIterator end<br /> )<br />{<br /> return ant_next_permutation(beg, end, std::greater<typename std::iterator_traits<BidirectionalIterator>::value_type>());<br />}</p> <p>template<class BidirectionalIterator, class BinaryPredicate><br />bool ant_prev_permutation(<br /> BidirectionalIterator beg,<br /> BidirectionalIterator end,<br /> BinaryPredicate op<br /> )<br />{<br /> /*//这里支持一般函数<br /> return ant_next_permutation( beg, end, std::not2(std::ptr_fun(op)) ); //先使用一般函数配接器，防止出现op为用户定义的普通函数，而not2出错<br /> //一般函数不能使用not1(op)或者not2(op)，所以先用ptr_fun(op)<br /> */<br /> return ant_next_permutation( beg, end, std::not2(op) );//这里只支持仿函数形式，不支持一般函数<br />}

//作者: Gods_巨蚁<br />//反馈方式<br />//E-mail:ljsunlin@126.com<br />//QQ:517377100<br />//Blog:http://hi.baidu.com/zhongji<br />//main.cpp<br />#include <iostream><br />#include <vector><br />#include <list><br />#include <algorithm><br />#include "Permutation.h" //模板必须把定义放到头文件里！！！<br />int main()<br />{<br /> std::list<int> coll1;<br /> for(int i = 1; i <= 3; ++i)<br /> coll1.push_back(i);<br /> /*do{<br /> std::copy(coll.begin(), coll.end(),<br /> std::ostream_iterator<int>(std::cout, " "));<br /> std::cout << "/n";<br /> }while( std::next_permutation(coll.begin(), coll.end()) );*/<br /> std::cout << "coll1: ant_next_permutation" << std::endl;<br /> do{<br /> std::copy(coll1.begin(), coll1.end(),<br /> std::ostream_iterator<int>(std::cout, " "));<br /> std::cout << "/n";<br /> }while( ant_next_permutation(coll1.begin(), coll1.end()) );<br /> std::cout << "coll1: ant_prev_permutation greater<int>" << std::endl;<br /> do{<br /> std::copy(coll1.begin(), coll1.end(),<br /> std::ostream_iterator<int>(std::cout, " "));<br /> std::cout << "/n";<br /> }while( ant_prev_permutation(coll1.begin(), coll1.end(), std::greater<int>()) );<br /> //coll2<br /> std::list<int> coll2;<br /> for(int i = 3; i >= 1; --i)<br /> coll2.push_back(i);<br /> std::cout << "coll2:ant_next_permutation greater<int>" << std::endl;<br /> do{<br /> std::copy(coll2.begin(), coll2.end(),<br /> std::ostream_iterator<int>(std::cout, " "));<br /> std::cout << "/n";<br /> }while( ant_next_permutation(coll2.begin(), coll2.end(), std::greater<int>()) );<br /> std::cout << "coll2:ant_prev_permutation" << std::endl;<br /> do{<br /> std::copy(coll2.begin(), coll2.end(),<br /> std::ostream_iterator<int>(std::cout, " "));<br /> std::cout << "/n";<br /> }while( ant_prev_permutation(coll2.begin(), coll2.end()) );<br /> system("PAUSE");<br />}