1-2全排列及其逆序数
- 格式:ppt
- 大小:1.89 MB
- 文档页数:10
§ 2 全排列及其逆序数一、全排列个不同元素排成一列。
可将个不同元素按1~ 进行编号,则个不同元素的全排列可看成这个自然数的全排列。
个不同元素的全排列共有种。
逆序的定义:取一个排列为标准排列,其它排列中某两个元素的次序与标准排列中这两个元素的次序相反时,则称这两个元素构成一个逆序。
通常取从小到大的排列为标准排列,即 1~ 的全排列中取123 为标准排列。
二、逆序及逆序数逆序数的定义:一个排列的逆序数的总数称为逆序数。
逆序数为偶数称为偶排列,逆序数为奇数称为奇排列,标准排列规定为偶排列。
逆序数的计算:设为的一个全排列,则其逆序数为其中为排在前,且比大的数的个数。
例:求的逆序数。
解:,逆序数算法在网上看了很多用mergesort求逆序数的代码,发觉很多都不太对,主要是在merge时求本次merge是前后两部分的逆序数过程,其实merge时由于前后两部分都是已经排好序的,假设merge的两个数组分别为a[n1],b[n2],合并时的逆序数就应该=b中所有小于a[1]的个数,小于a[2]的个数,小于a[3]的个数...小于a[n1]的个数之和=a中所有大于b[1]的个数,大于b[2]的个数,大于b[3]的个数...大于b[n2-1]的个数之和。
因此对于此次合并逆序数的个数有两种计算方法,一是以a中元素作为判断来计算,一是以b中元素作为判断来计算。
以a中元素作为为例:计算过程为,每当把a中某一个元素a[i]插入合并后的数组中时,计算b中已经插入合并后的数组中的元素个数ki,把这些所有的ki加起来即为本次合并的逆序数,具体的代码如下其中的iversion为逆序数。
int inversion=0;void merge(int* a,int p,int q,int r){int n1=r-p+1;int n2=q-r;int i,j,k;k=0;int *tmp=new int[n1+n2];for(i=p,j=r+1;i<=r&&j<=q;){if(a[i]<=a[j]){tmp[k]=a[i];inversion+=j-r;i++;k++;}else{tmp[k]=a[j];j++;k++;}}while(i<=r){tmp[k++]=a[i++];inversion+=q-r;}while(j<=q){tmp[k++]=a[j++];}for(i=p;i<=q;i++)a[i]=tmp[i-p];delete [] tmp;}如果所有人是线性排列,那我们的工作就是类似冒泡程序做的工作,,1,2,3,4,5变为5,4,3,2,1 ,耗时n(n-1)/2但是出现了环,也就是说1,2,3,4,5变为3,2,1,5,4也可满足条件我们可以把这个环等分成两个部分,每个部分看成是线性的,再把它们花的时间加起来. 当n是偶数时, 每份人数n/2 ,即(n/2-1)*(n/2)*2当n是偶数时,两份的人数分别是n/2和n-n/2,即(n/2-1)*(n/2)+ ((n-n/2)-1)*(n-n/2)/2*/int main(){int t,n,i,r,s;cin>>t;while(t--){cin>>n;if(n%2==0){r=n/2;s=(n/2-1)*(n/2);}else{r=n/2;n=n-r;s=(r-1)*r/2+(n-1)*n/2;}cout<<s<<endl;}return 0;}若是线形无环,将1-n变为n-1,求逆序数n*(n-1)/2即可(线性代数)但本题由于是环,则在1-n中取一k,将1-n 变为形如k-1,n-(k+1)也可满足条件,比如1,2,3,4,5变为3,2,1,5,4也可满足条件。