博客

全排列如果按字典顺序排好的话，我们知道其中的一个序列，就能推出下一个序列。比如说集合{1,2,3}的全排列按字典排序后如下：

1  2   3

1  3   2

2  1   3

2   3  1

3   1   2

3   2   1

当我们知道其中一个序列为{2,3,1}时，我们是可以推出下一个序列为{3,1,2}的，但是程序应该怎么写呢？主要分四步来找出下一个序列：

1.从右到左，找出当前序列中第一个违反递增规则的元素(相等不违反)记为pivot

2.从右到左，找出当前序列中第一个大于pivot的元素记为change

3.交换pivot和change的位置

4.将pivot位置（是交换之前的位置）右边的所有元素进行反转后得到的序列就是我们要的结果。

举个例子你应该就懂了：按上述方法求序列{6,8,7,4,3,2}的下一个序列的过程如下：

有了这个函数，我们只需要输入最小的序列然后不断求下一个序列，直到得到了最大的序列这样我们就能得到这个序列的全排列。其实STL已经为我们实现了这个函数next_permutation，所以如果是笔试我们可以直接用STL给的这个函数，但是要是面试的话还是需要我们自己实现这个函数。具体代码如下

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

template<typename Bidit>
bool my_next_permutation(Bidit first,Bidit last)    
{
	const auto rfirst=reverse_iterator<Bidit>(last);
	const auto rlast=reverse_iterator<Bidit>(first);
	auto pivot=next(rfirst);
	while(pivot!=rlast && (*pivot>=*prev(pivot)))   //第一步求pivot的位置
	{
		pivot=next(pivot);
	}
	if (pivot==rlast)                //判断当前序列是否是最大序列，如果是就返回false，同时将序列变为最小序列
	{
		reverse(rfirst,rlast);
		return false;
	}
	auto change=rfirst;
	while(change!=rlast && (*change<=*pivot))   //第二步求change位置
	{
		change=next(change);
	}
	swap(*pivot,*change);              //第三步交换pivot和change位置
	reverse(rfirst,pivot);             //反转pivot右边的所有的元素
	return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
	//全排列
	cout<<"全排列"<<endl;
	int inputArray[]={1,2,2,3};
	vector<int> inputVec(inputArray,inputArray+4);
	vector<vector<int>> result;
	do 
	{
		result.push_back(inputVec);
	} while (my_next_permutation(inputVec.begin(),inputVec.end()));
	for (int i=0;i<result.size();++i)
	{
		for (int j=0;j<result[i].size();++j)
		{
			cout<<result[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

程序运行结果如下：