首先,permutation指的是对元素的重排,比方a , b , c 三个元素的全部的重排为 abc, acb, bac,bca,cab,cba 总共 3! = 6 中情况,可是怎样声称这六种情况呢,C++标准库定义了函数 next_permutation,来生成一组元素的全部的全排列。首先。了解该函数的声明以及实现:
函数声明为: [摘自 www.cplusplus.com]
std::next_permutation
default (1) template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);custom (2) template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);此两者在C++的标准库中被实现为模板的形式。
參数说明:
first last
当中的迭代器 first 和 last 用来表示元素的范围 [ first, last ) 不正确称边界。再来就是该迭代器的类型为双向迭代器。那么也就是说 随机迭代器和双向迭代器能够作为该函数的參数传入。
Compare comp 是用来比較的函数,也就是说用来决定生成的重排的顺序函数。默认使用的是opeartor<符号,当然你自己也能够定义自己的比較函数,作为函数指针传入。或者是定义仿函数,传入函数对象,
返回值:
假设在该comp函数下。下一个重拍序列存在。则返回true。走则返回false,也就是说这一次的重拍序列已经是最后一个重排序列了。
比方,假设採用的是operator<作为比較函数的话,那么 {1,2,3}的最后一个重排就是321,第一个重排就是123,在321之后再调用next_premutation,返回false,可是该函数会将原来的数组排列为 1,2,3。
副作用:
该函数会改动传入的元素顺序。
#include #include int main() { int A[] = {1,3,2}; do{ std::cout << A[0] << " " << A[1] << " " << A[2] << std::endl; }while(std::next_permutation(A,A+3)); return 0; }
运行结果为:
能够看出,该函数会自己主动在当前的元素的顺序基础上。生成兴许的排列。也就是说。假设要生成全部的permutation的话,那么须要先将元素排序。
OK!!
使用方法已经具体解释了。接下来便是要将该函数的真面目示人了。
template <class _BidirectionalIter> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __last) //假设传入參数为空的话, return false; _BidirectionalIter __i = __first; ++__i; if (__i == __last) //假设仅仅有一个元素 return false; __i = __last; --__i; for(;;) { _BidirectionalIter __ii = __i; --__i; if (*__i < *__ii) { _BidirectionalIter __j = __last; while (!(*__i < *--__j)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; } if (__i == __first) { reverse(__first, __last); return false; } } }
以上为STL中的版本号,该函数实现原理例如以下:
在当前的序列中,从尾端出发往前找到一对相邻的元素 a[ i ] 与 a[ j ] ,使得 a[ i ] < a[ j ], (此处默认採用less函数对象)。然后再从尾端出发找到一个字符
a[ k ] ,使得 a[ i ] < a[ k ], 此时交换 a[ k ] 与 a[ i ], 而且将a[ j --- end) 之间的全部元素逆序就可以。代码实现为:
template<class bidirectional_iterator> bool permutation(bidirectional_iterator first, bidirectional_iterator last) { if(first == last) return false; //假设没有元素 if(first + 1 == last) return false; //假设仅仅有一个元素 bidirectional_iterator j = last; --j; while(1) { bidirectional_iterator i = j; --i; //find a[i] < a[j] and they are adjacent if(*i < *j) { bidirectional_iterator k = last; while(!(*i < *--k)){} std::iter_swap(i,k); //或者是 swap(*i, *k); std::reverse(j,last); return true; } --j; //no such a[i] < a[i+1] pair found if( j == first) { //restore the first of the permutation std::reverse(first, last); return false; } } }
上述代码中的swap函数必须是iter_swap函数。利用swap仅仅是交换了迭代器的指针,并未实际改变元素的位。也能够使用swap(*i, *k);
关于该函数的comp对象的实际形式,接着会有一篇关于函数指针以及函数对象的博文,具体解说。
2014 5.18 更新版本号
看到网上的一篇文章的求解全排列:
假设仅仅须要直接返回全部的全排列的话,那么非常easy,依次交换字符串中的相邻的字符就可以。
例如以下图:
原文链接: https://www.cnblogs.com/ldxsuanfa/p/10500893.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/291150
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!