[ALG] Counting Significant Inversions

[Verwijderd]

Heren,

Ik heb een beetje een probleempje met een algoritme wat ik aan het maken ben.

Het doel van het algoritme is om met behulp van Divide & Conquer een algoritme te schrijven dat uit een reeks positieve nummers het aantal significante inversies telt. Je doet dit door een variant van merge-sort te schrijven, waarbij je wat extra werk doet voor het tellen van de inversies.

Nu komt mijn probleem. Het tellen van normale inversions is geen probleem, maar ik zit een beetje in de knoei met mijn denken over significante inversies. Ik vind het moeilijk om een manier te bedenken waarmee ik (snel) die inversies kan tellen. Er moet een manier zijn waarop dat relatief snel kan, maar ik kan er niet opkomen.

Ik zal mijn probleem proberen te verduidelijken:

Ik heb de volgende getallenreeks: 10 4 2 7 3 1 5 6 0
Het aantal significante inversies in deze reeks is 16. Nu wil ik dit oplossen met divide en conquer.
Op een gegeven moment heb ik dus dit:

2 4 7 10

0 1 3 5 6

Het tellen van normale inversies in deze zou redelijk makkelijk zijn. Stel ik noem de bovenste lijst A, en de onderste lijst B. Je begint bij 2 in lijst A, en je vergelijkt dit getal met 0 in lijst B. 0 is kleiner dan 2, en dus wordt 0 het eerste getal in de gesorteerde lijst C. En aangezien 0 kleiner is dan alle getallen in A, wordt het aantal inversies opgehoogd met 4. Dan vergelijk je 1 met 2, 1 is kleiner, wordt toegevoegd aan C, en het aantal inversies wordt weer met 4 opgehoogd omdat alle getallen in A hoger zijn dan 1. Enzovoorts.
Als ik iets soortgelijks wil doen voor Significante inversies loop ik echter tegen een probleem op. Wil ik dat op dezelfde manier oplossen, zou dat in principe kunnen betekenen dat ik door een groot deel van lijst A steeds moet lopen. En dat kost heel veel tijd. (Toch?). Mijn vraag is dus of hier wat simpelers op te bedenken is, een foefje net als bij de gewone inversies. En is mijn denkwijze uberhaupt wel goed?

Is er iemand hier die me daarmee kan helpen? Ik zou het enorm waarderen!


PS: Ik weet niet zeker of mijn topic hier goed staat, ik zat een beetje te twijfelen tussen SEA en PRG, maar omdat het vooral over efficiëntie gaat, (als efficientie er niet toe doet, is dit probleem tamelijk makkelijk op te lossen, maar ik heb hier testcases klaar liggen met getallenreeksen van een paar miljoen (!) cijfers, met miljarden inversies.) Dus snelheid en efficientie is het belangrijkst..Vandaar SEA

[ Voor 33% gewijzigd door Verwijderd op 22-10-2007 23:46 ]

[Marcj]

Wil je even definieren wat "significant inversions" zijn? Want het enige zinnige wat ik erover kan vinden via google is dit:

quote: http://www.solutionlibrary.com/math/other/63429

You are given a sequence of n distinct numbers A1, ... , An. An inversion is a pair i < j such that Ai > Aj. Call a piar (i, j) a significant inversion if i < j and Ai > 2*Aj. Give an O(n*log(n)) algorithm to count the number of significant inversions in the input sequence.

Bedoel je dit? Ik kan me wel een algoritme voorstellen:

code:

origin = [10, 4, 2, 7, 3, 1, 5, 6, 0]
sorted = sort origin  -- O(n * log(n)), tenminste met quicksort

nrSR [x] _ = 0
nrSR (x:xs) sorted = let place = binSearch sorted (round (x/2)) -- O(log(n))
                         newSorted = binRemove sorted x         -- O(log(n))
                         in place + nrSR xs newSorted

Totaal is dit algoritme dus O(n * log(n) ) + O(n * (log(n) + log(n)) ) = O(n * log(n) ), want constanten vallen weg Hopelijk begrijp je een beetje wat ik bedoel.

Het algoritme in werking:

code:

step 1:
origin: 10 4 2 7 3 1 5 6 0
sorted: 0 1 2 3 4 5 6 7 10
index(5) = 5, total = 5

step 2:
origin: 4 2 7 3 1 5 6 0
sorted: 0 1 2 3 4 5 6 7
index(2) = 2, total = 7

step 3:
origin: 2 7 3 1 5 6 0
sorted: 0 1 2 3 5 6 7
index(1) = 1, total = 8

step 4:
origin: 7 3 1 5 6 0
sorted: 0 1 3 5 6 7
index(4) = 3, total = 11

step 5:
origin: 3 1 5 6 0
sorted: 0 1 3 5 6
index(2) = 2, total = 13

step 6:
origin: 1 5 6 0
sorted: 0 1 5 6
index(1) = 1, total = 14

step 7:
origin: 5 6 0
sorted: 0 5 6
index(3) = 1, total = 15

step 8:
origin: 6 0
sorted: 0 6
index(3) = 1, total = 16

step 9:
origin: 0, slechts een getal over, dus einde.

Resultaat = 16

[Verwijderd]

Dit is precies wat ik bedoel, maar je algoritme snap ik niet helemaal, kun je dit verder toelichten? Het algoritme moet overigens in O(n log n) kunnen...Dat is de bedoeling.. (Maar n * log(n) is hetzelfde..right?)

[ Voor 37% gewijzigd door Verwijderd op 23-10-2007 01:12 ]

[Marcj]

Ok, je begint met twee rijen, de originele en de gesorteerde rij (sorteren kan in O(n log n))

Dan doe je, zolang de lengte van de reeks nog groter is dan 1:
- x = eerst cijfer uit de originele rij
- place = plek waar round(x/2) staat (of zou staan), dit is tevens het aantal getallen dat kleiner is dan x/2 (met binairy search kan dit in O(log n))
- total += place, totale aantal ophogen
- verwijder x uit beide rijen, uit de originele rij gaat in O(1) en de gesorteerde in O(log n), als het goed is
- volgende iteratie

Wanneer dit klaar is heeft total het aantal significant inversions in O(n log n)

[Verwijderd]

Thx!

Inmiddels is het gelukt..:)