Soru Bir dizide inversiyonları sayma


Aşağıdakileri yapmak için bir algoritma tasarlıyorum: Verilen dizi A[1... n], her şey için i < j, tüm inversiyon çiftlerini bulun. A[i] > A[j]. A dizisini birleştirip A dizisini B dizisine alıyorum ve sonra iki diziyi karşılaştırarak kullanıyorum, ancak bunu, inversiyon sayısını bulmak için nasıl kullanabileceğimi görmek için zor bir zaman geçiriyorum. Herhangi bir ipucu veya yardım büyük takdir edilecektir.


84
2017-12-03 16:07


Menşei




Cevaplar:


Buna verebileceğim tek tavsiye (ev ödevi sorusu gibi görünen); ilk önce küçük sayıdaki sayılarla (ör. 5) manuel olarak yapmak ve sorunu çözmek için attığınız adımları yazmaktır.

Bu, kodu yazmak için kullanabileceğiniz genel bir çözüm bulmanızı sağlar.


40
2018-06-21 11:58



Bilgi için; soru aslında "ev ödevi" olarak etiketlenir. Bu soru henüz düzenlenmemiştir. Bu nedenle, bunu gönderdiğinde bunu etiketlemiş olması gerekir. - Doctor Jones
İyi bir nokta ... Öyleyse, ödevle ilgili bir kaynak olarak SO kullanarak öğrencileri alkışlarken, başka sorularda gördüğüm gibi, çözümün kendileri için kesilmesi ve yapıştırılması için doğrudan doğruya yazılması gerektiğinden emin değilim. :) - Andrew Rollings
Hayır, yapmamalıydı, ama kendisi için çözümü çözebilmek için yeterli bilgi verilmeli. Başka bir deyişle, ipuçları değil cevaplar. - Lasse Vågsæther Karlsen
Umarım ne yaptım. - Andrew Rollings
Bu kötü bir tavsiye değil, ama ya bir O (n ^ 2) algo'yu çözebilirsem? - Alcott


İşte burada javadaki O (n log n) çözümü.

long merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, count = 0;
    while (i < left.length || j < right.length) {
        if (i == left.length) {
            arr[i+j] = right[j];
            j++;
        } else if (j == right.length) {
            arr[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            arr[i+j] = left[i];
            i++;                
        } else {
            arr[i+j] = right[j];
            count += left.length-i;
            j++;
        }
    }
    return count;
}

long invCount(int[] arr) {
    if (arr.length < 2)
        return 0;

    int m = (arr.length + 1) / 2;
    int left[] = Arrays.copyOfRange(arr, 0, m);
    int right[] = Arrays.copyOfRange(arr, m, arr.length);

    return invCount(left) + invCount(right) + merge(arr, left, right);
}

Bu neredeyse normal birleştirme türüdür, bütün büyü birleştirme işlevinde gizlidir. Sıralama algoritmasını değiştirirken, inversiyonları kaldırdığınızı unutmayın. Birleştirme algoritması kaldırılan inversiyonların sayısını sayarken (biri sıralanabilir).

Algoritmanın bir dizinin sağ tarafından öğe alması ve onu ana diziye birleştirmesi, inversiyonların kaldırıldığı tek zamandır. Bu işlem tarafından kaldırılan inversiyon sayısı, birleştirilecek sol diziden kalan elemanların sayısıdır. :)

Umarım yeterince açıklayıcıdır.


118
2017-12-03 18:36



Bu daha temiz bir yöntem! - redDragonzz
Bunu çalıştırmayı denedim ve doğru cevabı almadım. Başlamak için main içinde invCount (intArray) aramanız mı gerekiyor? İntArray, int'nin sıralanmamış dizisi mi? Ben bir çok sayıda tam sayı ile koştum ve cevabım olarak -1887062008 aldım. Neyi yanlış yapıyorum? - nearpoint
+1, bakın benzer bir çözüm C ++ 11genel bir yineleyici tabanlı çözüm ve 5-25 elemandan diziler kullanarak rasgele test yatağı örneği dahil. Keyfini çıkarın!. - WhozCraig
Kod için +1 daha kısa ve anlaşılması kolay - Jerky
Bu bir çözüm değil. Çalıştırmayı denedim ve yanlış sonuçlar veriyor. - mirgee


Aşağıdaki yöntemle O (n * log n) zamanında buldum.

  1. A dizisini birleştirme ve bir kopya oluşturma (dizi B)
  2. A'yı [1] alın ve sıralı dizi B'deki konumunu ikili arama yoluyla bulun. Bu elemanın inversiyon sayısı, B'deki pozisyonunun indeks sayısından daha az olacaktır, çünkü A'nın birinci elementinden sonra görünen her bir alt sayı bir inversiyon olacaktır.

    2a. Değişken num_inversiyonları tersine çevirmek için inversiyon sayısını toplar.

    2b. A dizisinden A [1] ve aynı zamanda B dizisindeki karşılık gelen konumundan çıkar

  3. A'da daha fazla eleman kalmayıncaya kadar 2. adımdan tekrar çalışın.

Bu algoritmanın örnek bir örneği. Orijinal dizi A = (6, 9, 1, 14, 8, 12, 3, 2)

1: Sıralama ve B dizisine kopyala

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: B dizisinde bulmak için bir [1] ve ikili arama yapın

A [1] = 6

B = (1, 2, 3, 6, 8, 9, 12, 14)

6, B dizisinin 4. pozisyonundadır, dolayısıyla 3 inversiyon vardır. Bunu biliyoruz çünkü 6, A dizisinde birinci pozisyondaydı, böylece A dizisinde sonradan görünen herhangi bir düşük değerli eleman, j> i indeksine sahip olacaktır (çünkü ben bu durumda 1).

2.b: A [1] öğesini A dizisinden ve B dizisindeki karşılık gelen konumundan (kalın öğeler kaldırılır) kaldırın.

A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: Yeni A ve B dizilerinde 2. adımdan tekrar çalıştırın.

A [1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 şimdi B dizisinin 5. pozisyonundadır, dolayısıyla 4 inversiyon vardır. Bunu biliyoruz çünkü 9 A dizisindeki birinci pozisyondaydı, böylece daha sonra ortaya çıkan herhangi bir düşük değerli eleman, j> i indeksine sahip olacaktır (çünkü bu durumda yine 1). A [1] öğesini A dizisinden ve B dizisindeki karşılık gelen konumundan (kalın öğeler kaldırılır) kaldırın.

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)

Bu damarda devam etmek, döngü tamamlandıktan sonra A dizisi için toplam inversiyon sayısını bize verecektir.

Adım 1 (birleştirme sıralama) yürütmek için O (n * log n) alırdı. Adım 2, n kez yürütür ve her bir uygulamada, O (log n) toplam O (n * log n) için çalışacak bir ikili arama gerçekleştirir. Toplam çalışma süresi böylece O (n * log n) + O (n * log n) = O (n * log n) olur.

Yardım ettiğin için teşekkür ederim. Örnek dizileri bir parça kağıda yazmak, sorunu görselleştirmede gerçekten yardımcı oldu.


84
2018-03-01 05:20



neden birleştirme sıralama hızlı sıralama değil kullanın? - Alcott
@Alcott Hızlı sıralama, liste zaten sıralandığında O (n ^ 2) 'nin en kötü çalışma zamanına sahiptir ve ilk tur her turda seçilir. Birleşmenin en kötü durumu O (n log n) - user482594
Standart bir diziden kaldırma adımı, algoritma O (n ^ 2), değerleri kaydırdığından dolayı yapar. (Bu yüzden ekleme sırası O (n ^ 2)) - Kyle Butt
B dizisinin ilk elemanı ile başlayıp, A dizisinde öğelerin sayılmasından başlayarak, cevabınızda açıkladığınız gibi bunları ortadan kaldırmak şartıyla, aynı sonucu verir. - tutak
@el diablo n ^ 2 karmaşıklığı önlemek için elementler nasıl kaldırılır ?? - Jerky


Python'da

# O(n log n)

def count_inversion(lst):
    return merge_count_inversion(lst)[1]

def merge_count_inversion(lst):
    if len(lst) <= 1:
        return lst, 0
    middle = int( len(lst) / 2 )
    left, a = merge_count_inversion(lst[:middle])
    right, b = merge_count_inversion(lst[middle:])
    result, c = merge_count_split_inversion(left, right)
    return result, (a + b + c)

def merge_count_split_inversion(left, right):
    result = []
    count = 0
    i, j = 0, 0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count        


#test code
input_array_1 = []  #0
input_array_2 = [1] #0
input_array_3 = [1, 5]  #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5]  #5
input_array_7 = [4, 1, 3, 2, 9, 1]  #8

print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)

26
2018-04-21 16:40



Bu durumun +13'e ulaşmayı başarmasıyla şaşırdım - Python'da özellikle yetenekli değilim, ama hemen hemen aynı gibi görünüyor 2 yıl önce sunulan Java sürümübunun dışında herhangi bir açıklama yapmaz. Diğer her dilde cevap yazmak aktif olarak zararlı IMO'dur - muhtemelen daha fazla olmasa bile binlerce var, dil - Umarım hiç kimse bir soruya binlerce cevap vermemiz gerektiğini tartışır. Yığın Değişim bunun için yapılmadı. - Dukeling
@tennenrishin Tamam, belki de binlerce değil. Ama çizgiyi nerede çizeriz? Şu anda, saydığım gibi, on cevap veriyor aynı yaklaşım zaten. Bu hakkında Cevapların% 43'ü (cevapsız hariç) - burada sunulan yarım düzine başka yaklaşımın olduğu göz önüne alındığında oldukça yer kaplıyor. Aynı yaklaşım için sadece 2 cevap olsa bile, bu cevapları gereksiz yere sulandırır. Ve ben oldukça iyi bir argüman yaptım bu cevap özellikle Önceki yorumumda yararlı değil. - Dukeling
@Dukeling Senin gibi, Python'u bilmiyorum ve Java'ya daha aşina oldum. Bu çözümü Java'dan çok daha az okunabilir buluyorum. Bu nedenle, bazı insanlar için konuşmanın aynı ölçüde doğru olabileceği düşüncesine dayanır. - Museful
@tennenrishin Java'ya çok aşina oldum, henüz buldum üst düzey açıklama Java kodundan yüz kat daha okunabilir. Cevaplardaki diller değiştirilmiş olsaydı, cevabım muhtemelen aynı olurdu (ancak herhangi bir eski dil ya da ilk cevapta eski bir sözdizimi olmasaydı - her ikisi de herhangi biri tarafından okunması gereken çok yaygın bir sözdizimini kullanıyorlardı) terbiyeli programcı, iyi bir programcı, benzer bir sözdizimine sahip bir dil öğrenmiş olabileceği varsayımıyla). - Dukeling
Kullanıcıların büyük çoğunluğu için python sudo koduna yakındır. Açıkçası hiç bir açıklaması olmamasına rağmen, java'dan çok daha okunaklı bulabilirim. Bazı okurlara yardım ederse sinirlenmeye gerek yok. - Francisco Vargas


Kimsenin neden bahsetmediğini merak ediyorum ikili indeksli ağaçlar Henüz. Önek toplamlarını, permütasyon öğelerinizin değerleri üzerinde tutmak için birini kullanabilirsiniz. Sonra sağdan sola doğru ilerleyebilir ve her eleman için, sağdan küçük olan elemanların sayısını sayarsınız:

def count_inversions(a):
  res = 0
  counts = [0]*(len(a)+1)
  rank = { v : i+1 for i, v in enumerate(sorted(a)) }
  for x in reversed(a):
    i = rank[x] - 1
    while i:
      res += counts[i]
      i -= i & -i
    i = rank[x]
    while i <= len(a):
      counts[i] += 1
      i += i & -i
  return res

Karmaşıklık O (n log n) 'dir ve sabit faktör çok düşüktür.


15
2018-02-12 21:47



muhtemelen en iyi yaklaşım :) - Nilutpal Borgohain
@NilutpalBorgohain Teşekkürler :) En azından O (n log n) adayları arasında en az kod gerektiriyor gibi görünüyor. - Niklas B.
Bunun için teşekkürler. Anlamı nedir i -= i & -i hat? Ve benzer şekilde i += i & -i - Gerard Condon
@GerardCondon bu temelde BIT veri yapısı. Bunu açıklayan bir bağlantı cevapta bulunabilir - Niklas B.
Fenwick ağaçları hakkında TIL. Teşekkürler! Gönderdim Bir cevap bu bir timeit Bu soruya verilen tüm Python cevaplarının karşılaştırılması, kodunuzu içerir. Zamanlama sonuçlarına bakmak ilginizi çekebilir. - PM 2Ring


Aslında ev ödevi için benzer bir soru vardı. O (nlogn) verimliliğe sahip olması gerektiği sınırlandırıldı.

Mergesort'u kullanmayı önerdiğiniz fikri kullandım çünkü zaten doğru verimlilikten. Temel olarak birleştirme işlevine yeni kod ekledim: Sağdaki diziden bir sayı çıktı dizisine eklendiğinde, toplam inversiyon sayısına ve sol dizide kalan sayıya ekledim.

Bu, benim için yeterince düşünmüş olduğum için bana çok mantıklı geliyor. Sayıları saymadan önce kaç kez daha büyük bir sayı olduğunu hesaplıyorsunuz.

hth.


13
2018-04-04 20:38



cevabınızı destekliyorum, ikinci doğru dizinin elemanı çıktı dizisine kopyalandığında birleştirme işlevindeki birleştirme işlevindeki temel fark => 1 sol dizide kalan öğe sayısına göre artan inversiyon sayacı artar - Alex.Salnikov


Birleştirme sırasındaki birleştirme işlemini analiz ederek inversiyon sayısı bulunabilir: merge process

Bir elemanı ikinci diziden birleştirme dizisine (bu örnekte 9) kopyalarken, diğer öğelere göre yerini korur. Birinci diziden birleştirme dizisine (burada 5) bir öğe kopyalandığında, ikinci dizide kalan tüm elemanlarla (3 ve 4 ile 2 inversiyon) tersine çevrilir. Dolayısıyla, birleştirme türünün küçük bir değişikliği sorunu O (nnnn) 'de çözebilir.
Örnek olarak, sayımın olması için aşağıdaki mergesort python kodundaki iki # satırı uncomment.

def merge(l1,l2):
    l = []
    # global count
    while l1 and l2:
        if l1[-1] <= l2[-1]:
            l.append(l2.pop())
        else:
            l.append(l1.pop())
            # count += len(l2)
    l.reverse()
    return l1 + l2 + l

def sort(l): 
    t = len(l) // 2
    return merge(sort(l[:t]), sort(l[t:])) if t > 0 else l

count=0
print(sort([5,1,2,4,9,3]), count)
# [1, 2, 3, 4, 5, 9] 6

DÜZENLE 1

Aynı görev, biraz daha hızlı olduğu bilinen hızlı bir sıralama kararlı sürümü ile elde edilebilir:

def part(l):
    pivot=l[-1]
    small,big = [],[]
    count = big_count = 0
    for x in l:
        if x <= pivot:
            small.append(x)
            count += big_count
        else:
            big.append(x)
            big_count += 1
    return count,small,big

def quick_count(l):
    if len(l)<2 : return 0
    count,small,big = part(l)
    small.pop()
    return count + quick_count(small) + quick_count(big)

Pivotun son öğe olarak seçilmesiyle, tersine çevirmeler iyi sayılır ve yürütme süresi, yukarıdakileri birleştirmekten% 40 daha iyidir.

DÜZENLE 2 

Python'da performans için, numpy & numba sürümü:

Önce argsort O (nnnn) kullanan numpy parçası:

def count_inversions(a):
    n = a.size
    counts = np.arange(n) & -np.arange(n)  # The BIT
    ags = a.argsort(kind='mergesort')    
    return  BIT(ags,counts,n)

Ve verimli için numba parçası BIT yaklaşımı :

@numba.njit
def BIT(ags,counts,n):
    res = 0        
    for x in ags :
        i = x
        while i:
            res += counts[i]
            i -= i & -i
        i = x+1
        while i < n:
            counts[i] -= 1
            i += i & -i
    return  res  

10
2018-06-19 00:16



Gönderdim Bir cevap bu bir timeit Bu soruya verilen tüm Python cevaplarının karşılaştırılması, kodunuzu içerir. Zamanlama sonuçlarına bakmak ilginizi çekebilir. - PM 2Ring
Bu yayında hiçbir performans sorunu yok ... Bir süre deneyeceğim. Numpy numba izin verilir;)? - B. M.
Numba'yı hiç kullanmadım, ama Numpy'i biraz kullandım ve kendimden bir Numpy sürümü eklemeyi düşündüm, ancak testleri sadece standart kütüphaneyi kullanan çözümlerle sınırlandırmaya karar verdim. Ama bir Numpy çözümünün nasıl karşılaştırıldığını görmek ilginç olurdu. Küçük listelerde daha hızlı olmayacağından şüpheleniyorum. - PM 2Ring
100x hızlanma etkileyici! Ama ben Numba'm olmadığı için onu çalıştıramıyorum. Ve daha önce de söylediğim gibi, onu içine eklemek benim için adil olmaz. timeit Toplamak. - PM 2Ring