Successfully get arranged amounts of an arranged checklist

You have a rising checklist of numbers, what is one of the most reliable algorithm you can consider to get the rising checklist of amounts of every 2 numbers because checklist. Matches in the resulting checklist are unnecessary, you can remove them or prevent them if you such as.

To be clear, I'm interested in the algorithm. Do not hesitate to upload code in any kind of language and also standard that you such as.

2019-05-03 22:39:05
Source Share
Answers: 5


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


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)
2019-05-22 21:05:45

You can do this in 2 lines in python with

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

The price of this is n ^ 2 (possibly an added log variable for the set?) for the model and also s * log (s) for the arranging where s is the dimension of the set.

The dimension of the set can be as large as n * (n - 1)/ 2 as an example if X = [1,2,4, ...,2 ^ n ]. So if you intend to create this checklist it will certainly take at the very least n ^ 2/ 2 in the most awful instance given that this is the dimension of the result.

Nonetheless if you intend to select the first k components of the outcome you can do this in O (kn) making use of an option algorithm for arranged X+Y matrices by Frederickson and also Johnson (see here for gory details). Although this can possibly be changed to create them on-line by recycling calculation and also get a reliable generator for this set.

@deuseldorf, Peter There is some complication concerning (n!) I seriously question deuseldorf suggested "n factorial" yet merely "n, (really fired up)!"

2019-05-19 23:22:04

If you are seeking an absolutely language agnostic remedy after that you will certainly be sorely let down in my point of view due to the fact that you'll be stuck to a for loop and also some conditionals. Nonetheless if you opened it approximately useful languages or useful language attributes (I'm considering you LINQ ) after that my coworkers below can load this web page with classy instances in Ruby, Lisp, Erlang, and also others.

2019-05-07 19:59:41

The ideal I can think of is to generate a matrix of amounts of each set, and afterwards combine the rows with each other, a-la combine type. I seem like I'm missing out on some straightforward understanding that will certainly disclose a far more reliable remedy.

My algorithm, 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)

I located a small renovation, one that's even more responsive to careless stream-based coding. As opposed to combining the columns pair-wise, combine every one of them simultaneously. The benefit being that you start obtaining components of the checklist quickly.

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

Nonetheless, if you recognize you're mosting likely to make use of every one of the amounts, and also there's no benefit to obtaining several of them previously, select 'foldl merge []', as it's much faster.

2019-05-07 18:54:28

Rather than coding this out, I figure I'll pseudo-code it symphonious and also clarify my reasoning, to make sure that far better designers can jab openings in my reasoning if essential.

On the very first step we start with a checklist of numbers size n. For each number we require to create a checklist of size n-1 becuase we aren't including a number to itself. By the end we have a checklist of concerning n arranged checklists that was created in O (n ^ 2 ) time.

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 

Symphonious 2 due to the fact that the checklists were arranged deliberately (add a number per component in an arranged checklist and also the checklist will certainly still be arranged ) we can merely do a mergesort by combining each checklist with each other as opposed to mergesorting the entire great deal. Ultimately this needs to take O (n ^ 2 ) time.

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

The combine method would certainly be after that the regular combine action with a check to see to it that there are no replicate amounts. I will not write this out due to the fact that any person can seek out mergesort.

So there's my remedy. The whole algorithm is O (n ^ 2 ) time. Do not hesitate to mention any kind of blunders or renovations.

2019-05-07 17:31:57