微软笔试题 输出1到n的全排列

这里希望能更清楚，如果不好，欢迎拍砖。

12345的next是12354，从这里我们可以看出，next就是将大数字提到小数字的前面，即对调一个升序的两个数字。

而对于更一般的情况，对如下排列

234578

改变任意个升序的数字对都可以得到后续的排列。哪一个才是next呢?

当有多个升序的数对事，在高位对调，低位的对调会被跳过。我们应该先把低位的都改对调完再对调高位的。只有低位的是一个降序事，表明低位已经没有可以对调的了，

238754----（1）

当这个时候，才对调高位，如（1）这时候应该改变3，因为3后面的都比自己大，和后面的任何一个对调都可以。又因为后面已经是降序，所以最小的在最后，这样就和4对调。对调之后高位的4没问题了，3跑到了最后，此时4的后面仍然是一个降序。直接将这个降序改为升序就是next了。

所以现在的办法就是：

从而算法如下：

1. 从后往前在序列中找到第一对升序
2. 对调此升序，直到序列中没有升序

代码如下：

vector<int> & get_data(vector<int>& a,int num)
{
	a.clear();
	for (int i=1;i<=num;i++)
	{
		a.push_back(i);
	}
	return a;
}

typedef vector<int>::reverse_iterator riter;

bool exist_athwart(vector<int>& a,pair<riter,riter>& athwart)
{
	riter first=a.rbegin();
	for (riter i=first+1;i<a.rend();i++)
	{
		for (riter j=first;j<i;j++)
		{
			if (*j >  *i )
			{
				athwart=pair<riter,riter>(j,i);
				return true;
			}
		}
	}
	return false;

}

void permutaion(vector<int>& a)
{
	int num=1;
	cout<<num<<" : ";
	print(a.begin(),a.end());
	pair<riter,riter> athwart;
	while(exist_athwart(a,athwart))
	{
		swap(*athwart.first,*athwart.second);
		reverse(a.rbegin(),athwart.second);
		num++;
		cout<<num<<" : ";
		print(a.begin(),a.end());
	}
}

int main( void ) 
{

	vector<int> a;
	get_data(a,5);
	permutaion(a);
	return 0;
}