|
|
| |
|
| |
| |
| 含重复元素的排列生成算法 |
|
[ 2008-8-3 8:22:00 | By: wantnon ] |
任给一排列，生成稍大的排列。
例如：
传入112253321
返回112312235。
算法是：
112253321从右往左扫描，后五个数一直都上升，直到2处首次下降。
将2与后面比其稍大的数3互换得到112353221
然后将后五个数倒序即得到112312235。
程序：
bool nextlin(int a[],int N)//生成下一个排列
{
int i,j,k;
for(i=N-2;i>=0;i--)//从后往前走
{
if(a[i]<a[i+1])
break;
}//i定位在第一个降数
if(i==-1)//说明左->右一直升
{
return false;//返回false说明没有下一个了
}
int remberi=i;//把i值记录下来
for(j=N-1;j>=remberi+1;j--)//在N-1至remberi+1段上从左往右走
{
if(a[j]>a[remberi])
break;
}//找到第一个大于a[remberi]的数a[j]
//交换a[j]与a[remberi]
int temp=a[remberi];
a[remberi]=a[j];
a[j]=temp;
remberi++;//remberi前进一步
//将前当remberi至N-1段反序
for(k=1;k<=(N-remberi)/2;k++)
{
int temp=a[remberi+k-1];
a[remberi+k-1]=a[N-k];
a[N-k]=temp;
}
return true;//反回true说明计算下一个排列成功
}
|
|
| | |
|
