生成一个序列的全排列

　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>