Apakah ada cara untuk mengukur seberapa daftar diurutkan?

Maksud saya, ini bukan tentang mengetahui apakah suatu daftar diurutkan atau tidak (boolean), tetapi sesuatu seperti rasio "penyortiran", sesuatu seperti koefisien korelasi dalam statistik.

Sebagai contoh,

• Jika item daftar berada dalam urutan menaik, maka nilainya adalah 1,0

• Jika daftar diurutkan secara turun, nilainya akan -1.0

• Jika daftar hampir diurutkan naik, nilainya akan menjadi 0,9 atau nilai mendekati 1.

• Jika daftar tidak diurutkan sama sekali (acak), nilainya akan mendekati 0

Saya sedang menulis perpustakaan kecil di Scala untuk latihan. Saya pikir tingkat penyortiran akan berguna, tetapi saya tidak menemukan informasi tentang sesuatu seperti itu. Mungkin saya tidak tahu istilah yang memadai untuk konsep ini.

Anda cukup menghitung jumlah inversi dalam daftar.

Inversi

Suatu inversi dalam suatu urutan elemen-elemen tipe Tadalah sepasang elemen-elemen sekuens yang muncul tidak sesuai dengan beberapa pemesanan <pada set elemen T.

Dari Wikipedia :

Secara formal, biarkan A(1), A(2), ..., A(n)menjadi urutan nangka.
Jika i < jdan A(i) > A(j), maka pasangan (i,j)disebut inversi dari A.

Nomor inversi dari urutan adalah salah satu ukuran umum penyortirannya.
Secara formal, nomor inversi didefinisikan sebagai jumlah inversi, yaitu,

Untuk membuat definisi ini lebih jelas, pertimbangkan urutan contoh 9, 5, 7, 6. Urutan ini memiliki inversi (0,1), (0,2), (0,3), (2,3) dan nomor inversi 4 .

Jika Anda menginginkan nilai antara 0dan 1, Anda dapat membagi nomor inversi dengan N choose 2.

Untuk benar-benar membuat algoritma untuk menghitung skor ini untuk bagaimana diurutkan daftar itu, Anda memiliki dua pendekatan:

Pendekatan 1 (Deterministik)

Ubah algoritma penyortiran favorit Anda untuk melacak berapa banyak inversi yang dikoreksi saat dijalankan. Meskipun ini bukan trivial dan memiliki implementasi yang bervariasi tergantung pada algoritma pengurutan yang Anda pilih, Anda akan berakhir dengan algoritma yang tidak lebih mahal (dalam hal kompleksitas) daripada algoritma pengurutan yang Anda mulai.

Jika Anda mengambil rute ini, perlu diketahui bahwa tidak sesederhana menghitung "swap". Mergesort, misalnya, adalah kasus terburuk O(N log N), namun jika dijalankan pada daftar yang diurutkan dalam urutan menurun, itu akan memperbaiki semua N choose 2inversi. Itu O(N^2)inversi diperbaiki di O(N log N)operasi. Jadi beberapa operasi pasti mengoreksi lebih dari satu inversi pada suatu waktu. Anda harus berhati-hati dengan implementasi Anda. Catatan: Anda dapat melakukan ini dengan O(N log N)kerumitan, itu hanya rumit.

Terkait: menghitung jumlah "inversi" dalam permutasi

Pendekatan 2 (Stochastic)

• Pasangan sampel secara acak (i,j), di manai != j
• Untuk setiap pasangan, tentukan apakah list[min(i,j)] < list[max(i,j)](0 atau 1)
• Hitung rata-rata perbandingan ini dan kemudian normalkan dengan N choose 2

Saya pribadi akan pergi dengan pendekatan stokastik kecuali jika Anda memiliki persyaratan ketepatan - jika hanya karena sangat mudah diimplementasikan.

Jika yang benar-benar Anda inginkan adalah nilai ( z') antara -1(diurutkan menurun) ke 1(diurutkan naik), Anda cukup memetakan nilai di atas ( z), yang antara 0(diurutkan naik) dan 1(diurutkan turun), ke rentang ini menggunakan rumus ini :

z' = -2 * z + 1

Ukuran tradisional tentang bagaimana diurutkan daftar (atau struktur berurutan lainnya) adalah, adalah jumlah inversi.

Jumlah inversi adalah jumlah pasangan (a, b) st indeks a <b DAN b <<a. Untuk tujuan ini <<mewakili hubungan pemesanan apa pun yang Anda pilih untuk jenis khusus Anda.

Daftar yang sepenuhnya diurutkan tidak memiliki inversi, dan daftar yang sepenuhnya terbalik memiliki jumlah inversi maksimum.

Anda dapat menggunakan korelasi aktual.

Misalkan untuk setiap item dalam daftar diurutkan, Anda menetapkan peringkat integer mulai dari nol. Perhatikan bahwa grafik indeks posisi elemen versus peringkat akan terlihat seperti titik-titik dalam garis lurus (korelasi 1,0 antara posisi dan peringkat).

Anda dapat menghitung korelasi pada data ini. Untuk pengurutan terbalik, Anda akan mendapatkan -1 dan seterusnya.

Ada jawaban yang bagus, dan saya ingin menambahkan aspek matematika untuk kelengkapan:

• Anda dapat mengukur seberapa daftar diurutkan dengan mengukur seberapa banyak itu berkorelasi dengan daftar yang diurutkan. Untuk melakukan itu, Anda dapat menggunakan korelasi peringkat (yang paling dikenal adalah Spearman's ), yang persis sama dengan korelasi biasa, tetapi menggunakan peringkat elemen dalam daftar, bukan nilai analog dari item-itemnya.

• Ada banyak ekstensi, seperti koefisien korelasi (+1 untuk pengurutan yang tepat, -1 untuk inversi yang tepat)

• Ini memungkinkan Anda untuk memiliki properti statistik untuk ukuran ini, seperti teorema batas pusat permutasional, yang memungkinkan Anda untuk mengetahui distribusi ukuran ini untuk daftar acak.

Terlepas dari jumlah inversi, untuk daftar angka, jarak kuadrat rata-rata dari status yang diurutkan dapat dibayangkan:

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

Saya tidak yakin dengan metode "terbaik", tetapi yang sederhana adalah membandingkan setiap elemen dengan yang sesudahnya, menambah penghitung jika elemen2> elemen 1 (atau apa pun yang ingin Anda uji) dan kemudian dibagi dengan jumlah total elemen. Itu akan memberi Anda persentase.

Saya akan menghitung perbandingan dan membaginya dengan jumlah total perbandingan. Berikut ini adalah contoh Python sederhana .

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result

Bagaimana dengan sesuatu yang seperti ini?

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()

Jika Anda mengambil daftar Anda, menghitung peringkat nilai-nilai dalam daftar itu dan memanggil daftar peringkat Ydan daftar lain, Xyang berisi bilangan bulat dari 1hingga length(Y), Anda bisa mendapatkan ukuran pengurutan yang Anda cari dengan menghitung koefisien korelasi ,, di rantara dua daftar.

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}} 

Untuk daftar yang sepenuhnya diurutkan r = 1.0,, untuk daftar yang diurutkan terbalik r=-1.0,, dan perbedaan rantara batas-batas ini untuk berbagai tingkat pengurutan.

Masalah yang mungkin terjadi dengan pendekatan ini, tergantung pada aplikasinya, adalah bahwa menghitung peringkat setiap item dalam daftar sama dengan menyortirnya, sehingga ini merupakan operasi O (n log n).