用O(NlogN)的時間比較兩個序列的差異

Problem Definition

• given two sequences of the same item set, compute how many order relations are different
• order relation: a < b < c vs. c < a < b, in this case, there are two different relations which are (a, c) and (b, c)

Sample inputs and their results:

• [a, b, c], [c, b, a] -> 3
• [a, b, c, d], [d, a, b, c] -> 3
• [a, b, c, d], [d, a, c, b] -> 4, the different order relations are (a, d), (b, c), (b, d), (c, d)

Algorithm

想法

展開所有可能的order relation需要C(N, 2)次，N是item set的大小，聽Oshin說有O(NlogN)的方法，用Merge Sort的概念即可。昨天睡不著想了兩個小時，感覺差一環就想通了。今早起來忽然想通關鍵的merge，利用已排好的特性，merge的時間只要O(n)。

Pseudo Code

大概寫寫，邊界沒有算很準，陣列由1開始算，R[1..m]的意思是R的sub sequence，範圍是1..m。

CompSeq(R, R’)
Input：R, R’ which are sequences (e.g. R = [a, b, c], R’ = [b, c, a])
Output：n, the number of different order relations

1. for each c in R, H[c] := index of c in R, where H is a hash table
2. return CompSubSeq(R’)

CompSubSeq(R)

1. return 0 if |R| = 1
2. let m := |R| / 2, R1 := R[1..m], R2 := R[(m+1)..|R|]
3. return CompSubSeq(R1) + CompSubSeq(R2]) + Merge(R1, R2)

Merge(R1, R2)

1. let n := 0, k1 := 1, k2 := 1 and R be a new array
2. for i in 1..(|R1|+|R2|) do:
3. if k2 > |R2| or (k1 < = |R1| and Smaller(R1[k1], R2[k2])),
   then R[i], k1 := R1[k1], k1+1
4. else R[i], k2, n := R2[k2], k2+1, n+|R1|-k1+1
5. end for
6. return n

Smaller(a, b)

1. return true if H[a] < H[b]

雜記

Ruby寫的版本見這裡，原本想寫完整版的測試，寫完演算法後懶了，果然應該先寫test code再開始寫，才不會懶得寫test code啊。

可以利用如下的方法實作test code：產生(a1, a2, …, an) item set的所有排列，在產生排列的同時，可以知道目前產生的是第幾組序列，得到序列值後，可以用O(N)的方法算出差了幾個relation，以(a, b, c, d)和(d, c, a, b)為例，(d, c, a, b)是第23個序列，23 = 3*3! + 2*2! + 0*1! + 1*0!，所以是3 + 2 = 5次；以(c, d, a, b)來說，這是第17個序列，17 = 2*3! + 2*2! + 0*1! + 1*0!，所以是2 + 2 = 4次。利用餘數的技巧，序列數轉成階乘表示只要O(N)。

昨天原本想用這個序列順序轉答案的方法來解這問題，大部份的思考在這裡打轉。雖然成功地將原問題reduce成找序列順序的問題，並且可以用O(N)的方法由序列順序算出答案，但想不到O(NlogN)算出序列順序的方法。