Count Inversions
コンピューター科学と離散数学では、 転倒は 自然な順番に並んでいない要素の配列の場所のペアである。 番号のグループを昇順で使うとしたら転倒とは大きい番号が小さい番号の前に現れる時である。
この配列の例をチェックしてみましょう。 (1, 2, 5, 3, 4, 7, 6) には3つの転倒があります。
- 5 と 3
- 5 と 4
- 7 と 6
あなたはユニークな番号の配列が与えられ、その配列の転倒数を数えなくてはいけません。
入力 配列が整数のタプルとして与えられる
出力 転倒数を整数として出力する
例
count_inversion*1 == 3
count_inversion*2 == 0
どうやって使われるか このミッションではネストされたループの不思議を経験することになるでしょう、 もちろんもしあなたが高度なアルゴリズムを使わなければですが。
事前条件 2 < len(sequence) < 200
len(sequence) == len(set(sequence))
all(-100 < x < 100 for x in sequence)
def count_inversion(sequence): """ Count inversions in a sequence of numbers """ current_number = sequence[0] first_count_loop = 0 second_count_loop = 0 result = 0 length = len(sequence) while first_count_loop < length: second_count_loop = first_count_loop + 1 current_number = sequence[first_count_loop] while second_count_loop < length: if current_number > sequence[second_count_loop]: result += 1 second_count_loop += 1 first_count_loop += 1 return result if __name__ == '__main__': #These "asserts" using only for self-checking and not necessary for auto-testing assert count_inversion((1, 2, 5, 3, 4, 7, 6)) == 3, "Example" assert count_inversion((0, 1, 2, 3)) == 0, "Sorted" assert count_inversion((99, -99)) == 1, "Two numbers" assert count_inversion((5, 3, 2, 1, 0)) == 10, "Reversed"
すぐにはわからなかった。test =（1,2,5,3,4,7,6)というタプルで動きを考えてみる。
まず添字０から基準をはじめる。test[0]の値は１なので、これと右の数字を比較していく。本来の順番であれば、すべて右にいくほど（添字があがっていくほど）大きい値になるはず。
だから、test[0] = 1 より小さいのがあればカウンターをまわしていく。
右端まで行ったら、おわり。つぎは添字を一つ増やしてtest[1]について同様に比較していく。
という考え方で解いた。つまり、問題文にもあったようにループは２つ必要となる。
現在の数字を保存する変数と、外側のループ、内側のループを管理する変数が必要。
first_count_loopじゃなくて、first_loop_countのほうが良い名前だった…。
あとは素直に書いた。一応動く。
Clear
def count_inversion(sequence): return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))
ワンライナーだ。知らなかった関数は、以下の通り
enumerate(iterable, start=0)¶(原文)
enumerate オブジェクトを返します。 iterable は、シーケンスか iterator か、あるいはその他のイテレーションをサポートする何らかのオブジェクトでなければなりません。 enumerate() によって返されたイテレータの __next__() メソッドは、 (デフォルトでは 0 となる start からの) カウントと、 iterable 上のイテレーションによって得られた値を含むタプルを返します。
>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]
次と等価です:
def enumerate(sequence, start=0):
n = start
for elem in sequence:
yield n, elem
n += 1
sum(iterable[, start])
start と iterable の要素を左から右へ合計し、総和を返します。 start はデフォルトで 0 です。 iterable の要素は通常は数値で、start の値は文字列であってはなりません。
使う場面によっては、 sum() よりもいい選択肢があります。文字列からなるシーケンスを結合する高速かつ望ましい方法は ''.join(sequence) を呼ぶことです。浮動小数点数値を拡張された精度で加算するには、 math.fsum() を参照下さい。一連のイテラブルを連結するには、 itertools.chain() の使用を考えてください。
Speedly
def M(l,r): if l+1>=r: return 0 if l+2==r: if A[l]<=A[l+1]: return 0 A[l],A[l+1]=A[l+1],A[l] return 1 m = (l+r)//2 i=l j=m k=l cl=M(l,m) cr=M(m,r) c=0 while i<m and j<r: if A[i]<=A[j]: W[k]=A[i] k+=1 i+=1 else: W[k]=A[j] k+=1 j+=1 c+=m-i while i<m: W[k]=A[i] k+=1 i+=1 while j<r: W[k]=A[j] k+=1 j+=1 for i in range(l,r): A[i]=W[i] return cl+cr+c <200b> def count_inversion(a): global A,W A=list(a) W=[0]*len(A) return M(0,len(A)) <|| これはマージソートというらしい。 計算量がO(nlogn)なので大量になると早いみたい。
