首页 > 代码库 > 利用标准库算法求解排列组合

利用标准库算法求解排列组合

2024-07-17 08:17:08   228人阅读

以前求序列的排列时，最常用的方法就是递归回溯，现在发现其实像这样有特定算法的重复性工作是可以在STL标准库中找到答案的。
在STL的变序性算法中，有两个用于排列元素的算法分别如下：
bool next_permutation(Iterator beg,Iterator end)

bool prev_permutation(Iterator beg,Iterator end)

这两个算法的功能也很简单，next_permutation()会改变区间(beg,end)内的元素次序，使它们符合"下一个排列次序"，即next_permutation会使序列朝着降序序列变化，每次调用都只调整一对次序，如还未达到降序则返回true,达到降序后返回false.

prev_permutation会使序列朝着升序变换，每次调用也只会调整一对次序，达到升序后返回false否则都返回true.

所以循环调用这两个算法时，将会得出序列由当前序列变换成相应的升序或降序的每一个过程，如果起始序列本身为升序再朝着降序方向变换或起始序列本身为降序朝着升序方向变换，将自然会得出该序列所有全排列组合。

具体的示例如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;

class A
{
public:
	A(int d):a(d){}
	~A(){}
	int operator()()
	{
		return ++a;
	}
private:
	int a;
};
template<int b>
int fun()
{
	static int a = b;
	return --a;
}
int main()
{
	vector<int> vec;
	generate_n(inserter(vec,vec.begin()),3,A(0));
	//起始序列（升序）
	cout<<"起始序列：";
	copy(vec.begin(),vec.end(),ostream_iterator<int>(cout,"--"));
	cout<<endl;
	//next_permutation将原序列变换为朝向降序的下一个序列，直到序列变成降序为止
	while (next_permutation(vec.begin(),vec.end()))
	{
		copy(vec.begin(),vec.end(),ostream_iterator<int>(cout,"--"));
		cout<<endl;
	}
	vector<int> vec1;
	generate_n(inserter(vec1,vec1.begin()),4,fun<4>);
	//起始序列（降序）
	cout<<"起始序列：";
	copy(vec1.begin(),vec1.end(),ostream_iterator<int>(cout,"->"));
	cout<<endl;
	//prev_permutation将原序列变换为朝向升序的下一个序列，直到序列变换成升序为止
	while (prev_permutation(vec1.begin(),vec1.end()))
	{
		copy(vec1.begin(),vec1.end(),ostream_iterator<int>(cout,"->"));
		cout<<endl;
	}
}

结果图如下：


联系
我们