逆序對演算法

A. 一道ACM題，求逆序對問題

一． 預備知識

.

這部分就是網路上一搜一大片的東西，不過還是強調一下。

.

1． 全排列

從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m＝n時所有的排列情況叫n的全排列。[1]對於n的全排列，共有n!種情況。

2. 逆序、逆序數和奇、偶排列

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[2]

例如，對於n=3的全排列：

全排列

123

231

312

132

213

321

逆序數

0

2

2

1

1

3

奇偶性

偶

奇

.

二． 相關問題

.

1. 給定一個排列，求它的逆序數。[3]

問題：給定一個排列，求它的逆序數是多少。
分析：設 p1,p2,…,pn 為n的一個全排列，則其逆序數為t=t1+t2+…+tn=

其中 ti為排在pi 前，且比pi 大的數的個數。

這部分代碼比較簡單，此處略去。

.

2. 根據逆序數推排列數。[4]

問題：給定一個n元排列，它的逆序數存在且唯一。那麼反過來，已知一個n元排列的逆序數為m，
這樣的n元排列有多少種？
分析：我們用f(n,m)表示逆序數為m的n元排列的個數,則求滿足條件的排列個數問題就轉化為求f(n,m)的值的問題。

為了得到最終結果，我們先研究f(n,m)的性質。可以得到以下幾個命題：

[命題1] 對任意n>=2且0<=m<=C(n,2)時f(n,m)>=1；當m>C(n,2)時,f(n,m)=0

C(a,b)表示從a個元素中選出b個元素的選擇種數

證明：先證命題1的前半部分。

(1)n=2時，m只可能是0或1.有f(2,0)=1,f(2,1)=1

(2)假設n=k時命題成立,即有f(k,m)>=1(0<=m<=C(k,2))

當n=k+1時，排列1,2,3,…,k+1滿足逆序數為0,所以有f(k+1,0)>=1

若m>=1，考慮某一逆序數為m-1的k元排列a1,a2,…,ak(由歸納假設知這個排列存在).現將k+1插入到a(k-1)和ak之間得到一個k+1元排列a1,a2,…,a(k-1),k+1,ak，這個排列的逆序數為m,所以f(k+1,m)>=1

綜上所述，對所有的0<=m<=C(n,2)有f(n,m)>=1

再證命題的後半部分(比較顯然)。

因為對於一n元排列，若要使其逆序數達到最大，那麼排列中任兩個數都構成逆序，其逆序數為C(n,2)，所以不可能存在一n元排列使其逆序數大於C(n,2)

[命題2] f(n,m)=f(n,C(n,2)-m)

證明：對於一個逆序數為m的n元排列a1,a2,…,an，n元排列an,a(n-1),…,a2,a1的逆序數為C(n,2)-m.同理，對於一個逆序數為C(n,2)-m的n元排列a1,a2,…,an，n元排列an,a(n-1),…,a2,a1的逆序數為m.

於是，逆序數為m的n元排列的集合 和 逆序數為C(n,2)-m的n元排列的集合 是一一對應關系，所以f(n,m)=f(n,C(n,2)-m)

[命題3] f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)

先考慮由1,2,…,n組成的一個排列a1,a2,…,an，由於任一個由1,2,…,n,n+1構成的排列，可以看成將n+1加入的a1左邊，或an的右邊，或ai與a(i+1)之間(1<=i<=n-1)而形成的。又由於在n+1加入任一個位置之後，其前面沒有比n+1大的數，其後面的數都比n+1小，而且加入n+1之後，使得對後面的每一個數而言，其前面比自身大的數的個數增加1，對n+1前面的數而言，其前面比自身大的個數不變。於是當選取n+1加入a1的左邊時，排列a1,a2,…,an的逆序數變為m+n，當n+1加入ai與a(i+1)之間(1<=i<=n-1)時，排列a1,a2,…,an的逆序數變為m+n-i，當加入an的右邊時，排列a1,a2,…,an的逆序數仍為m。

於是，對於任一逆序數為m的n+1元排列，考慮n+1所處的位置。若n+1在第k位，則其餘n個元素構成逆序數為m-n+k-1的n元排列，且對任一逆序數為m-n+k-1的n元排列而言，當n+1放在該排列的某位，使得在新排列中n+1處於第k位，那麼新排列成為一逆序數為m的n+1元排列。

於是，逆序數為m的n+1元排列的集合 和 逆序數為m的n元排列的集合 是一一對應關系。這樣，對於一個n+1元排列，f(n,m)表示n+1排在最後的排列個數，f(n,m-1)表示n+1排在倒數第二位的排列的個數……，f(n,m-n)表示n+1排在首位的排列個數，且f(n+1,m)為這些排列之和。

所以f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)(注:記b<0時，f(a,b)=0)

[命題4] f(n,0)=f(n,C(n,2))=1

[命題5] f(n,1)=f(n,C(n,2)-1)=n-1(n>1)

證明：由命題3和命題4有

f(n,1)=f(n-1,1)+f(n-1,0)=f(n-1,1)+1

反復應用上式，根據f(2,1)=1，得到命題5成立

[命題6] f(n,2)=f(n,C(n,2)-2)=C(n,2)-1(n>2)

證明：由命題3，4，5有

f(n,2)=f(n-1,2)+f(n-1,1)+f(n-1,0)=f(n-1,2)+n-1

反復應用上式，根據f(2,2)=0，得到命題6成立

同理，可證明

f(n,3)=C(n,3)-C(n,2)-C(n,1) (n>3)

f(n,4)=C(n,4)+2C(n,3)-C(n,1) (n>4)

f(n,5)=C(n,5)+3C(n,4)+2C(n,3)-C(n,2)+1 (n>5)

…

我們可以無限遞推下去，計算f(n,k)的時候要用到前面所推導出的f(n,1)~f(n,k-1)。但是卻很難得到一個通項公式。這個問題就類似於用∑(k^t-(k-1)^t) 來求∑(k^(t-1))，每作下一項都要用到前面所有的結果。

由於在命題3中我們得出了一個關於f(n,m)的遞推公式，而且又知道了一些初始值。因此可以設計一個程序，輸入n,m，輸出f(n,m)。[5]

.

參考代碼：

+ View Code
.
3. 根據每個數的逆序數，然後求出原排列。[6]

復制代碼
問題：對於一個集合S={1,2,3,...N}的任一排列a1、a2、a3、... aN，我們定義ai的逆序數為
∑(aj>ai | j<i)，即排在ai前的所有比ai大的數的個數。我們把每個數的逆序數按下標排出就構
成排列a1、a2、a3、... aN的一個逆序排列。比如排列 3 1 2 的逆序排列為 1 1 0(從左往右
依次是1的逆序數、2的逆序數、3的逆序數)。現在我們給出一個排列的逆序排列，請求出原排列。[7]
復制代碼
分析：<developing…一種題解請參閱引用7>

.

4. 給定逆序數，求滿足此逆序數的最小排列。[8]

問題：對於n的全排列，給定一個正整數m，找到滿足逆序數是m的最小的排列。例如，n=5，m=4，此
時滿足逆序數為4最小的排列是1 3 5 4 2。
分析：解決此問題，要先了解以下幾個命題和定理。（注意，在證明中排列的大於、小於指兩排列在全排列中位置的前後關系，小於即在前，大於反之）

[定理1]對於n的全排列，在它完全倒序的時候（也就是n,n-1,…,2,1的時候）逆序數最多。

證明：此處省略，可用反證法簡單證明。

[命題1]對於一個形如1,2,3,…,i-1,i,n,…i+1的排列q（如n=5時的1,2,5,4,3），即在數n前保證首項為1且嚴格以公差為1遞增而數n之後排列任意的數列，

(1)當數n之後是遞減的時候q的逆序數最多，為t=C(n-i,2)。

(2)排列q是出現逆序數為t的最小排列。

證明：首先證明(1)。

這個證明很容易。因為數列的前i+1項已經確定，所以整個數列的逆序數只和i+2項到n項有關。顯然，由定理1，當第i+2項到第n項完全倒序的時候逆序數最大。比如說排列1,2,5,4,3就比1,2,5,3,4構成的逆序對多。

現在證明(2)。

假設存在一個排列p的逆序數為m且p小於q。我們知道，q的前i位已經是數n在當前位置的最小排列。也就是說，在q中無論是n還是n之後的任意一個數，將它與q中的1到i位的任意一個數更換位置後得到的排列一定大於q。比如，對於排列q：1,2,5,4,3，前兩個數1、2的位置是不能變的，否則會大於q，比如1,3,5,4,2。

所以我們只能從q的第i+1位到n位入手。由(1)可知，當n在第i+1位時，無論後面的數怎麼排列，逆序數都無法超過m。所以p的數n一定在第i+2到第n位的任一位上。

好的，我們假設數n在第i+2位上。在這種情況下不難發現，我們把原來n後面最大的數填補到第i+1位，這時的逆序數最多。比如對於1,2,5,4,3，我們把5移動到第4位，然後將4填補到第3位，排列就變成了1,2,4,5,3，顯然這要比1,2,3,5,4優。

我們分析一下這時p的逆序數。因為數n到了第i+2位，則由它構成的逆序數為n-i-2。同樣，由第i+1位（也就是例子中的4，即n-1）構成的逆序數也是n-i-2。顯然，由於保持了遞減的特徵，剩下的第i+3到第n位的逆序數為C(n-i-2,2)。（這里姑且認為C(1,2)=1）這時總的逆序數為

t1 =C(n-i-2,2)+2*(n-i-2)

=(n-i-2)(n-i-3)/2+2*(n-i-2)

=(n-i-2)(n-i+1)/2.

而q的逆序數

t2=C(n-i,2)

=(n-i)(n-i-1)/2.

用t2-t1，得到定值1。也就是說，無論n取何值，t2總是大於t1。

如果再將數n向右移動一位，這時我們只有保持前1到i+1位（即例子中的1,2,3,4）不變才能夠保證之後的變換能夠使逆序數最大（這個很顯然，不特別證明）。然而，當前面的i+1位確定了以後，怎麼變換後面的數字才能夠使總逆序數最大呢？還是要原來n後面最大的數填補到第i+1位。我們已經證明，這樣做是不如不換優的。所以，不存在一個小於q的排列p使p的逆序數為m。證畢。

[命題2]在命題1所設定的排列q的基礎上，我們將數n後面的第k小數與數n的前一個數（即i）交換，然後使數n後面保持逆序。這樣得到的新排列所含的逆序數為t=C(n-i,2)+k，且這個排列是逆序數為t的最小排列。

證明：首先，在此強調一下排列q的結構，如圖一：

由於操作以後數n之後仍然保持逆序，所以從第i+1到第n位的逆序數仍為C(n-i,2)。對於x來說，交換之前後面有k-1個比它小的數，交換之後又加上了一個，所以x所擁有的逆序數（即以x為左的逆序數）為k-1+1=k,此時總的逆序數為C(n-i,2)+k。

對於新排列逆序數為t=C(n-i,2)+k的最小排列的證明與命題1的證明相似，在此處不加以詳細證明。

到此我們可以得出，命題2也是真命題。

有了這兩個命題作基礎，我們很容易就能夠得到這道題的演算法。首先利用命題1，二分查找找到數n的位置，我們可以得到數n在這個位置的時候形如q的排列的逆序數t。然後計算t與m的差值，得出k，然後根據命題2進行變換，最後得出要求的排列。

.

參考代碼：

+ View Code

B. 逆序數怎麼求

解答如下：

當n=1時，排列為1 2，逆序數t=0。

當n=2時，排列為內1 3 2 4，逆序容數t=1。

當n=3時，排列為1 3 5 2 4 6，逆序數t=1+2=3。

當n=4時，排列為1 3 5 7 2 4 6 8，逆序數t=1+2+3=6。

當n=5時，排列為1 3 5 7 9 2 4 6 8 10，逆序數t=1+2+3+4=10。

相關內容解釋

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。

也就是說，對於n個不同的元素，先規定各元素之間有一個標准次序(例如n個 不同的自然數，可規定從小到大為標准次序)，於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。

C. 什麼叫逆序

跟標准列相反序數的總和
比如說
標准列是1 2 3 4 5
那麼 5 4 3 2 1 的逆序數演算法：
看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個
類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個
同樣的，2 之前有3個，1之前有4個
將這些數加起來就是逆序數=1+2+3+4=10

再舉一個 2 4 3 1 5
4 之前有0個
3 之前有1個
1 之前有3個
5 之前有0個
所以逆序數就是1+3=4

這樣能明白嗎

D. 當排列數中出現相同的數時，逆序數怎麼計算，比如145243

一．
預備知識
.
這部分就是網路上一搜一大片的東西，不過還是強調一下。
.
1．
全排列
從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m＝n時所有的排列情況叫n的全排列。[1]對於n的全排列，共有n!種情況。
2.
逆序、逆序數和奇、偶排列
在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[2]
例如，對於n=3的全排列：
全排列
123
231
312
132
213
321
逆序數
0
2
2
1
1
3
奇偶性
偶
奇
.
二．
相關問題
.
1.
給定一個排列，求它的逆序數。[3]
問題：給定一個排列，求它的逆序數是多少。
分析：設
p1,p2,…,pn
為n的一個全排列，則其逆序數為t=t1+t2+…+tn=
其中
ti為排在pi
前，且比pi
大的數的個數。
這部分代碼比較簡單，此處略去。
.
2.
根據逆序數推排列數。[4]
問題：給定一個n元排列，它的逆序數存在且唯一。那麼反過...

E. 給定有序表A[1:n]，修改合並排序演算法，求出該有序表的逆序對數

逆序對是這么定義的，在數組array中，如果存在下標i，j ，且 i<j ,但是array[i]>array[j]。這里假定array是升序的，如果是降序則相反就行。
比如說 1，5，4，3 則有逆序對 （5，3）（5，4）（4，3）

顯然最笨的求逆序對的方法是，兩層循環查找一遍，復雜度為O（n^2）;
目前最好的求逆序對的方法就是用分治法，也就是和歸並排序類似的方法。

我大概說一下這種方法的思想，有什麼不明白的直接用網路hi我。

首先將數組array從中間一分為二，假設前半部分叫left，後半部分叫right
那麼，可以先遞歸地對left和right做歸並排序，同事順便求出它們的逆序對數;(你學歸並排序了，這個應該能懂吧？)
然後，也就是最重要的一步，這時候left和right已經是有序的了，設置下標，l和r分別指向left和right的頭，如果當前的l指向的元素大於r指向的元素，則r++（這時候就構成逆序對了，因為left中的元素在原數組中的下標一定小於right中的元素），一直到left[l]<=right[r]為止，這時候l++，最終到left或right掃描完終止。這其實也是歸並排序的歸並過程。

F. 逆序對的求解逆序對個數問題

方法一：最原始的方法，利用兩重循環進行枚舉。該演算法的時間復雜度為O(n^2)。
C++代碼如下： intcount_inversion(int*a,intN){intcount=0;inti,j;for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(a[i]>a[j])count++;returncount;}Pascal代碼如下： vari,j,k,n:longint;a:array[1..1000000]oflongint;beginreadln(n);fori:=1tondoread(a[i]);k:=0;fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]theninc(k);writeln(k);end.方法二：利用歸並排序的思想求解逆序對的個數，這是解決該問題的一種較為高效的演算法。該演算法的時間復雜度為O(nlogn)。
C++代碼如下： voidmerge_inversion(int*a,intl,intm,intr){inti,j,k;intn1=m-l+1;intn2=r-m;int*L=(int*)calloc(n1,sizeof(int));int*R=(int*)calloc(n2,sizeof(int));for(i=l;i<=m;i++)L[i-l]=a[i];for(j=m+1;j<=r;j++)R[j-m-1]=a[j];i=0;j=0;for(k=l;k<=r;k++){if(i<n1&&j<n2){if(L[i]<R[j]){a[k]=L[i++];globa_count+=n2-1-j+1;}elsea[k]=R[j++];}elsebreak;}//(i==n1&&j<n2)while(j<n2)a[k++]=R[j++];if(i<n1&&j==n2)while(i<n1)a[k++]=L[i++];free(L);free(R);}Pascal代碼如下： Typearr=array[1..1000000]oflongint;Vari,n:longint;k:int64;a,b:arr;Proceremerge(vara:arr;l,x,r:longint);vari,j,p:longint;//p:positionbegini:=l;j:=x+1;p:=l;while(p<=r)dobeginif(i<=x)and((j>r)or(a[i]<=a[j]))thenbeginb[p]:=a[i];inc(i);endelsebeginb[p]:=a[j];inc(j);inc(k,x-i+1);end;inc(p);end;fori:=ltordoa[i]:=b[i];end;Proceremsort(vara:arr;l,r:longint);varx:longint;beginif(l<>r)thenbeginx:=(l+r)div2;msort(a,l,x);msort(a,x+1,r);merge(a,l,x,r);end;end;Beginreadln(n);fori:=1tondoread(a[i]);k:=0;msort(a,1,n);writeln(k);End.

G. n階行列式逆序數怎麼算，有沒有具體公式一步將逆序數

沒有具體公式，演算法如下：

在行列式：

顯然，1,2,...,n也是一個n級排列，這個排列具有自然順序，就是按遞增的順序排起來的；其它的排列都或多或少地破壞自然順序。

逆序

定義2 在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。

註：

1.對於n個不同的元素，先規定個元素之間有一個「標准次序」（例如n個不同的自然數，可規定由小到大為標准次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就有1個「逆序」。

2.一個排列中所有逆序的總數叫做這個排列的逆序數。

3.逆序數為奇數的排列叫做奇排列，逆序數為偶數的排列叫做偶排列。

H. 一道編程題：求逆序對的個數

#include<stdio.h>
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)/*去掉相同的元素，再進行排序*/
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}

printf("%d\n%d",k,m);
}//呵呵，我只會用c寫，不過結果是對的。

I. 怎麼算逆序數急~~~！！！

可使用直接計數法，計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。

舉個例子：

標准列是1 2 3 4 5，那麼 5 4 3 2 1 的逆序數演算法：

看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個。

類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個。

同樣的，2 之前有3個，1之前有4個，將這些數加起來就是逆序數=1+2+3+4=10。

(9)逆序對演算法擴展閱讀：

其它演算法：

1、歸並排序

歸並排序是將數列a[l,h]分成兩半a[l,mid]和a[mid+1,h]分別進行歸並排序，然後再將這兩半合並起來。在合並的過程中（設l<=i<=mid，mid+1<=j<=h），當a[i]<=a[j]時，並不產生逆序數；

當a[i]>a[j]時，在前半部分中比a[i]大的數都比a[j]大，將a[j]放在a[i]前面的話，逆序數要加上mid+1-i。因此，可以在歸並排序中的合並過程中計算逆序數。

2、樹狀數組

由於樹狀數組的特性，求和是從當前節點往前求，所以，這里要查詢插入當前數值之時，要統計有多少個小於該數值的數還沒插入，這些沒插入的數，都會在後面插入，也就形成了逆序數。