下一个序列.cpp

主要是输出一个排列的后一个序列

#include<iostream>
using namespace std;

# define N 100

void swap(int& a,int& b)
{
	int t=a;
	a=b;
	b=t;
}

void reverse(int p[],int beg,int des)
{
	if(beg==des) return;
	else if(beg+1==des)
	{
		swap(p[beg],p[des]);	
	}

	else
	{
		int mid=(beg+des)/2;
		int r;
		for(r=beg;r<=mid;r++)
		{
			swap(p[r],p[des-r+beg]);//+beg是偏移量
		}
	}
}

int *next_perm(int *p,int n)
{
	int i,j,k;
	for(j=n;j>=2;j--) 
			{
				if(p[j-1]<p[j]) 
				{
					i=j;
					//printf("the selected i is: %d\n",i);
					break;
				}
			}
			
			for(k=n;k>=1;k--) //求出比a[i-1]大的数 
			{
				if(p[i-1]<p[k]) 
				{
					j=k;
					//printf("the selected j is: %d\n",j);
					break;
				}
			}

			swap(p[i-1],p[j]);//然后交换 

			/*printf("the permutation after the 1st swapping is:\n");
			for(k=1;k<=n;k++)
			{
				printf("%d ",p[k]);
			}
			printf("\n");*/
			
			reverse(p,i,n);//再从a[i]到a[n]逆置 

			return p;
}

int main()
{
    int i,n;
    int a[N];
    while(cin>>n&&n)
    {
                 int *p;
                 for(i=1;i<=n;i++)
                 cin>>a[i];
                 p=next_perm(a,n);
                 for(i=1;i<=n;i++)
                 cout<<a[i];
                 
    }
    system("pause");
    return 0;
}