输出一到n的全排列

输出1到n的全排列

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

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

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

234578

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

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

238754    ----（1）

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

所以现在的办法就是：

从而算法如下：

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

代码如下：

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;}