Effektivt få sortert summer av en sortert liste

stemmer
17

Du har en stigende liste med tall, hva er den mest effektive algoritmen du kan tenke på å få stigende listen over summer hver to tall i den listen. Duplikater i resultatlisten er irrelevant, kan du fjerne dem eller unngå dem hvis du vil.

For å være klar, er jeg interessert i algoritmen. Føl deg fri til å poste kode på alle språk og paradigmet som du liker.

Publisert på 03/08/2008 klokken 21:08
kilden bruker
På andre språk...                            


8 svar

stemmer
12

Rediger pr 2018: Du bør nok slutte å lese dette. (Men jeg kan ikke slette det som det er akseptert.)

Hvis du skriver ut summene som dette:

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

Du vil merke at siden M [i, j] <= M [i, j + 1] og M [i, j] <= M [i + 1, j], så du trenger bare å undersøke øverst til venstre " hjørner" og velge det laveste.

f.eks

  • bare en øvre venstre hjørne, plukke 2
  • bare ett, plukke 5
  • 6 eller 8, plukke 6
  • 7 eller 8, plukke 7
  • 9 eller 8, 8 plukke
  • 9 eller 9, plukke begge :)
  • 10 eller 10 eller 10, plukke alt
  • 12 eller 11, plukke 11
  • 12 eller 12, plukke både
  • 13 eller 13, plukke både
  • 14 eller 14, plukke både
  • 15 eller 16, plukke 15
  • bare ett, plukke 16
  • bare ett, plukke 17
  • bare ett, plukke 18

Selvfølgelig, når du har massevis av topp venstre hjørne da denne løsningen tilfaller.

Jeg er ganske sikker på at dette problemet er Ω (n²), fordi du må beregne summene for hver M [i, j] - med mindre noen har en bedre algoritme for oppsummering :)

Svarte 18/09/2008 kl. 21:41
kilden bruker

stemmer
4

Snarere enn koding ut dette, jeg figuren jeg vil pseudo-kode det i trinn og forklare min logikk, slik at bedre programmerere kan stikke hull i min logikk hvis det er nødvendig.

På det første skrittet vi starte med en liste med tall lengde n. For hvert nummer må vi lage en liste over lengde n-1 fordi vi ikke legger til et nummer i seg selv. Ved slutten har vi en liste over omtrent n sortert lister som ble generert i O (n ^ 2) tid.

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 

I trinn 2 fordi listene er sortert etter design (legge et nummer til hvert element i en sortert liste, og listen vil fortsatt bli sortert) kan vi bare gjøre en mergeSort ved å slå sammen hver liste sammen i stedet for mergesorting hele mye. Til slutt bør dette ta O (n ^ 2) tid.

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

Flettingen metoden ville være så normal flettingen takt med en sjekk for å være sikker på at det ikke er like summer. Jeg vil ikke skrive ut dette fordi alle kan se opp mergeSort.

Så det er min løsning. Hele algoritmen er O (n ^ 2) tid. Føl deg fri til å påpeke eventuelle feil eller forbedringer.

Svarte 03/08/2008 kl. 23:06
kilden bruker

stemmer
2

Du kan gjøre dette på to linjer i python med

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

Kostnaden for dette er n ^ 2 (kanskje en ekstra log faktor for settet?) For iterasjonen og s * log (r) for sortering, hvor s er størrelsen av apparatet.

Størrelsen av settet kan være så stor som n * (n-1) / 2 for eksempel dersom X = [1,2,4, ..., 2 ^ n]. Så hvis du ønsker å generere denne listen vil det ta minst n ^ 2/2 i verste fall siden dette er størrelsen på produksjonen.

Men hvis du ønsker å velge de første k elementer av resultatet du kan gjøre dette i O (KN) ved hjelp av et utvalg algoritme for sortert X + Y matriser av Fred og Johnson ( se her for blodige detaljer) . Selv om dette kan nok bli endret for å generere dem på nettet ved å gjenbruke beregning og få en effektiv generator for dette settet.

@deuseldorf, Peter Det er litt forvirring om (n!) Jeg alvorlig tvil deuseldorf betydde "n faktoriell", men bare "n, (veldig begeistret)!"

Svarte 11/08/2008 kl. 14:47
kilden bruker

stemmer
1

Uansett hva du gjør, uten ytterligere begrensninger på inngangsverdiene, du kan ikke gjøre det bedre enn O (n ^ 2), rett og slett fordi du må iterere gjennom alle par av tall. Iterasjonen vil dominere sortering (som man kan gjøre i O (n log n) eller raskere).

Svarte 18/09/2008 kl. 22:15
kilden bruker

stemmer
1

Dette spørsmålet har vært wracking hjernen min for ca en dag nå. Rått.

Anyways, du kan ikke komme bort fra n ^ 2 natur det lett, men du kan gjøre litt bedre med sammenslåingen, siden du kan bundet området for å sette inn hvert element i.

Hvis du ser på alle listene du genererer, de har følgende form:

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

Hvis du snur den 90 grader, får du:

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

Nå bør sammenslåingen være å ta to lister iog i+1(som tilsvarer lister der det første medlemmet er alltid a[i]og a[i+1]), kan du bundet området for å sette elementet (a[i + 1], a[j])inn liste iav plasseringen av (a[i], a[j])og plasseringen av (a[i + 1], a[j + 1]).

Dette betyr at du bør fusjonere i revers når det gjelder j. Jeg vet ikke (ennå) hvis du kan utnytte dette på tvers jogså, men det synes mulig.

Svarte 21/08/2008 kl. 18:16
kilden bruker

stemmer
1

I 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);
}
Svarte 08/08/2008 kl. 23:05
kilden bruker

stemmer
1

Det beste jeg kunne komme opp med er å produsere en matrise av summer hvert par, og deretter flette radene sammen, a-la merge sort. Jeg føler at jeg mangler noen enkle innsikt som vil avsløre en mye mer effektiv løsning.

Min algoritmen, i 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)

Jeg har funnet en mindre forbedring, en som er mer mottagelig for lat streambasert koding. I stedet for å slå sammen kolonnene parvis, flette dem alle på en gang. Fordelen er at du begynner å få elementer av listen umiddelbart.

-- 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

Men hvis du vet at du kommer til å bruke alle summene, og det er ingen fordel å få noen av dem tidligere, gå med ' foldl merge []', som det er raskere.

Svarte 03/08/2008 kl. 21:36
kilden bruker

stemmer
-4

Hvis du er ute etter en virkelig språk agnostiker løsning vil du bli dypt skuffet etter min mening fordi du vil bli sittende fast med en for løkke og noen conditionals. Men hvis du åpnet den opp til funksjonelle språk eller funksjonelle språkfunksjoner (jeg ser på deg LINQ) så mine kolleger her kan fylle denne siden med elegante eksempler i Ruby, Lisp, Erlang, og andre.

Svarte 03/08/2008 kl. 21:24
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more