Doeltreffend te kry gesorteer bedrae van 'n gesorteerde lys

Question

Jy het 'n stygende lys van getalle, wat is die mees doeltreffende algoritme wat jy kan dink om die stygende lys van bedrae elke twee getalle in die lys te kry. Duplikate in die gevolglike lys is irrelevant, kan jy dit verwyder of te vermy hulle as wat jy wil.

Om duidelik te wees, Ek stel belang in die algoritme. Voel vry om kode te plaas in enige taal en paradigma wat jy wil.

Answer 1

Edit as van 2018: Jy moet waarskynlik ophou lees van hierdie. (Maar ek kan dit nie verwyder as dit aanvaar word.)

As jy skryf uit die somme soos volg:

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

Jy sal sien dat daar sedert M [i, j] <= M [i, j + 1] en M [i, j] <= M [i + 1, j], dan hoef jy net die ondersoek top left "hoeke" en kies die laagste een.

Bv.

• net 1 boonste linkerhoek, tel 2
• net 1, haal 5
• 6 of 8, pluk 6
• 7 of 8, kies 7
• 9 of 8, tel 8
• 9 of 9, tel beide:)
• 10 of 10 of 10, haal al
• 12 of 11, tel 11
• 12 of 12, tel beide
• 13 of 13, tel beide
• 14 of 14, tel beide
• 15 of 16, tel 15
• net 1, tel 16
• net 1, tel 17
• net 1, tel 18

Natuurlik, wanneer jy baie van links bo hoeke dan wentel hierdie oplossing.

Ek is redelik seker dat hierdie probleem is Ω (n²), want jy het die somme te bereken vir elke M [i, j] - tensy iemand 'n beter algoritme vir die opsomming:)

Answer 2

In plaas van kodering dit uit, ek vind ek pseudo-kode dit in stappe en verduidelik my logika, sodat beter programmeerders gate in my logika kan steek indien nodig.

Op die eerste stap ons begin met 'n lys van getalle lengte N. Vir elke nommer moet ons 'n lys van lengte N-1 te skep becuase ons is nie 'n nommer toe te voeg tot self. Teen die einde het ons 'n lys van ongeveer N gesorteer lyste wat gegenereer in O (n ^ 2) keer.

step 1 (startinglist) 
for each number num1 in startinglist
   for each number num2 in startinglist
      add num1 plus num2 into templist
   add templist to sumlist
return sumlist 

In stap 2 omdat die lyste is gesorteer volgens ontwerp (voeg 'n aantal aan elke element in 'n gesorteerde lys en die lys sal steeds gesorteer) ons kan eenvoudig 'n mergesort doen deur die samesmelting van elke lys saam eerder as mergesorting die hele lot. Op die ou end moet hierdie O neem (n ^ 2) keer.

step 2 (sumlist) 
create an empty list mergedlist
for each list templist in sumlist
   set mergelist equal to: merge(mergedlist,templist)
return mergedlist

Die merge metode sal dan die normale merge stap met 'n tjek om seker te maak dat daar geen dubbele somme. Ek sal dit nie uitskryf want niemand kan opkyk mergesort.

Daar is dus my oplossing. Die hele algoritme is O (n ^ 2) keer. Voel vry om daarop te wys enige foute of verbeterings.

Answer 3

Jy kan dit doen in twee lyne in python met

allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)

Die koste hiervan is N ^ 2 (miskien 'n ekstra log faktor vir die stel?) Vir die iterasie en s * log (s) vir die sortering waar s is die grootte van die set.

Die grootte van die set kan so groot soos n * word (N-1) / 2 byvoorbeeld as X = [1,2,4, ..., 2 ^ n]. So as jy wil om hierdie lys te genereer sal dit ten minste neem N ^ 2/2 in die ergste geval, want dit is die grootte van die uitset.

Maar as jy wil hê dat die eerste k elemente van die uitslag kies jy kan dit doen in O (kn) met behulp van 'n seleksie algoritme vir gesorteer X + Y matrikse deur Frederickson en Johnson ( sien hier vir gruwelike besonderhede) . Hoewel dit waarskynlik kan verander word om dit aanlyn te genereer deur hergebruik berekening en kry 'n doeltreffende generator vir hierdie reeks.

@deuseldorf, Peter Daar is 'n paar verwarring oor (N!) Ek ernstig twyfel deuseldorf bedoel "N faktoriaal" maar net "n, (baie opgewonde)!"

Answer 4

Die beste wat ek kon kom met is om 'n oorsig van somme elke paar saam te produseer, en dan saam te smelt die rye, a-la merge soort. Ek voel asof ek mis 'n paar eenvoudige insig dat 'n baie meer doeltreffende oplossing sal openbaar.

My algoritme, in Haskell:

matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]

sortedSums = foldl merge [] matrixOfSums

--A normal merge, save that we remove duplicates
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case compare x y of
    LT -> x:(merge xs (y:ys))
    EQ -> x:(merge xs (dropWhile (==x) ys))
    GT -> y:(merge (x:xs) ys)

Ek het 'n klein verbetering, een wat meer vatbaar vir lui-stroom gebaseer kodering. In plaas van die samesmelting van die kolomme paarsgewyse, saam te smelt almal op een slag. Die voordeel is dat jy begin om elemente van die lys onmiddellik.

-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists
-- wideNubMerge does this while eliminating duplicates
wideNubMerge :: Ord a => [[a]] -> [a]
wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls
wideNubMerge1 [] = []
wideNubMerge1 ls = mini:(wideNubMerge rest)
    where mini = minimum $ map head ls
          rest = map (dropWhile (== mini)) ls

betterSortedSums = wideNubMerge matrixOfSums

As jy egter weet jy gaan al die somme te gebruik, en daar is geen voordeel te kry 'n paar van hulle vroeër, gaan met 'foldl merge []', want dit is vinniger.

Answer 5

In SQL:

create table numbers(n int not null)
insert into numbers(n) values(1),(1), (2), (2), (3), (4)


select distinct num1.n+num2.n sum2n
from numbers num1
inner join numbers num2 
    on num1.n<>num2.n
order by sum2n

C # LINQ:

List<int> num = new List<int>{ 1, 1, 2, 2, 3, 4};
var uNum = num.Distinct().ToList();
var sums=(from num1 in uNum
        from num2 in uNum 
        where num1!=num2
        select num1+num2).Distinct();
foreach (var s in sums)
{
    Console.WriteLine(s);
}

Answer 6

Dit maak nie saak wat jy doen, sonder bykomende beperkings op die insetwaardes, jy kan nie beter as O doen (n ^ 2), bloot omdat jy hoef te herhaal deur die hele pare van getalle. Die iterasie sal oorheers sorteer (wat jy kan doen in O (n teken N) of vinniger).

Answer 7

Hierdie vraag is tergend my brein vir ongeveer 'n dag nou. Awesome.

In elk geval, kan jy nie maklik weg te kom van die N ^ 2 aard daarvan, maar kan jy 'n bietjie beter doen met die merge sedert jy die reeks kan verplig om elke element in te voeg.

As jy kyk na al die lyste wat jy genereer, hulle het die volgende vorm:

(a[i], a[j]) | j>=i

As jy dit flip 90 grade, kry jy:

(a[i], a[j]) | i<=j

Nou, moet die merge proses neem twee lyste i en i+1 (wat ooreenstem met lyste waar die eerste lid altyd a[i] en a[i+1]), kan jy die reeks beslis element (a[i + 1], a[j]) in lys i voeg by die plek van (a[i], a[j]) en die plek van (a[i + 1], a[j + 1]).

Dit beteken dat jy moet saamsmelt in reverse in terme van j. Ek weet nie (nog) as jy dit oor j sowel kan benut, maar dit lyk moontlik.

Answer 8

As jy op soek is na 'n ware taal agnostikus oplossing dan sal jy baie teleurgesteld in my opinie, want jy sal vas met 'n for-lus en 'n paar conditionals. Maar as jy dit oop tot funksionele tale of funksionele taal funksies (Ek is op soek na jou LINQ) dan my kollegas hier kan hierdie bladsy vul met elegante voorbeelde in Ruby, Lisp, Erlang, en ander.