生成一个序列的全排列

　2012-05-26 07:47:26　来源：WEB开发网　闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚�

闂傚倸鍊风粈渚€骞夐敓鐘插瀭闁汇垹鐏氬畷鏌ユ煙閹殿喖顣奸柛搴＄У閵囧嫰骞掗幋婵冨亾閻㈢ǹ纾婚柟鐐灱濡插牊绻涢崱妤冃℃繛宀婁簽缁辨捇宕掑鎵佹瀸闂佺懓鍤栭幏锟�

濠电姷鏁告慨顓㈠箯閸愵喖宸濇い鎾寸箘閹规洟姊绘笟鈧ḿ褍煤閵堝悿娲Ω閳轰胶鍔﹀銈嗗笂閼冲爼鍩婇弴銏＄厪闁搞儮鏅涙禒褏绱掓潏鈺佷槐闁轰焦鎹囬弫鎾绘晸閿燂拷闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚�　　闂傚倸鍊烽懗鑸电仚缂備胶绮〃鍛村煝瀹ュ鍗抽柕蹇曞У閻庮剟姊虹紒妯哄闁圭⒈鍋嗛惀顏囶樄闁哄本娲樼换婵婄疀閺囩姷鐛ラ梻浣哄帶婢瑰﹥绂嶅⿰鍫氣偓鏃堝礃椤忎礁浜鹃柨婵嗛婢ь喖霉閻樻瑥瀚粻楣冩煕椤愩倕鏋庨柣蹇嬪劜閵囧嫰寮村Ο鍝勫Е濡炪們鍨洪悷鈺呭箖閳╁啯鍎熼柕鍥у簻閹凤拷

核心提示：之前写过全排列的程序，昨天做poj 1731的时候又遇到了，生成一个序列的全排列，发现自己以前把各个方法基本都试过了，这里总结一下下面几种方法：方法一：把全排列转换为树的遍历，当前排列已经是最大的排列，所以不存在下一个，可以使用深度优先遍历，也可以使用广度优先遍历（需要存储大量中间数据

之前写过全排列的程序，昨天做poj 1731的时候又遇到了。发现自己以前把各个方法基本都试过了。

这里总结一下下面几种方法：

方法一：把全排列转换为树的遍历，可以使用深度优先遍历，也可以使用广度优先遍历（需要存储大量中间数据，内存要求大）。具体实现可以用递归，也可用非递归。

方法二：根据当前的排列，交换元素，生成下一个，然后再生成下一个。。。。。。

比如有个字符序列acdef，当前排列为acfed,则从后向前找到第一个比d大的字母c,交换得adfec，然后把d后面的字母从小到大排序得adcef。

看了STL中next_permutation的源码码之后，很庆幸，原来自己的想法跟库里的实现方法是一样的，但是如何找到第一个大的字母，如何对后面排序没想太明白，于是具体实施的效率跟STL有天壤之别。

linux下的next_permutation源码码，在文件/usr/include/c++/4.1.2/bits/stl_algo.h中。

next_permutation的文档 http://www.sgi.com/tech/stl/next_permutation.html

cplusplus中next_permutation的文档 http://www.cplusplus.com/reference/algorithm/next_permutation/

下面让我们分析一下STL中next_permutation的实现代码:

<span style="font-size:18px;"> /**
 *  @brief  Permute range into the next @a dictionary ordering.
 *  @ingroup sorting_algorithms
 *  @param  first  Start of range.
 *  @param  last　 End of range.
 *  @return  False if wrapped to first permutation, true otherwise.
 *
 *  Treats all permutations of the range as a set of @a dictionary sorted
 *  sequences.  Permutes the current sequence into the next one of this set.
 *  Returns true if there are more sequences to generate.  If the sequence
 *  is the largest of the set, the smallest is generated and false returned.
 */
template<typename _BidirectionalIterator>
　 　   bool
next_permutation(_BidirectionalIterator __first,
　 　  　  　   _BidirectionalIterator __last)
{
　 　   // concept requirements
　 　   __glibcxx_function_requires(_BidirectionalIteratorConcept<
　 　  　  　  　  　   _BidirectionalIterator>)
　 　  　  　   __glibcxx_function_requires(_LessThanComparableConcept<
　 　  　  　  　  　  　  　   typename iterator_traits<_BidirectionalIterator>::value_type>)
　 　  　  　   __glibcxx_requires_valid_range(__first, __last);

　 　   if (__first == __last) //序列为空，则返回false
　 　  　  　   return false;
　 　   _BidirectionalIterator __i = __first;
　 　   ++__i;
　 　   if (__i == __last)//序列中元素个数为1，返回false
　 　  　  　   return false;
　 　   __i = __last;
　 　   --__i; //i指向最后一个元素

　 　   for(;;)
　 　   {
　 　  　  　   _BidirectionalIterator __ii = __i;
　 　  　  　   --__i;
　 　  　  　   if (*__i < *__ii)　　　　　   
　 　  　  　  　  　   //循环，直到找到相邻的两个元素，前面的元素比后面的大  比如此例子中__i指向c,__ii指向f
　 　  　  　   {
　 　  　  　  　  　   _BidirectionalIterator __j = __last;
　 　  　  　  　  　   while (!(*__i < *--__j))　　　　　　　 //从序列末尾找到一个比__i大的元素 此例子中__i 指向c,__j指向d
　 　  　  　  　  　   {}
　 　  　  　  　  　   std::iter_swap(__i, __j);　　　  //交换c ,d
　 　  　  　  　  　   std::reverse(__ii, __last);　  //交换完c,d之后，后面的序列肯定是从大往小的，
　 　  　  　  　  　   因此直接reverse即可实现从小到大排序
　 　  　  　  　  　  　  　   return true;　　　　　　　　　  //返回true
　 　  　  　   }
　 　  　  　   if (__i == __first)　　　　　　　　  //整个序列从后向前遍历一遍，没有找到相邻的两个元素使得前面的元素
　 　  　  　  　  　   大于后面的元素，因此，当前排列已经是最大的排列，所以不存在下一个，结束。
　 　  　  　  　  　   {
　 　  　  　  　  　  　  　   std::reverse(__first, __last);
　 　  　  　  　  　  　  　   return false;
　 　  　  　  　  　   }
　 　   }
}

</span>