成功获得安排的清单金额

你有一个不断上升的数字清单,你可以考虑采用哪种最可靠的算法来获得每2个数字的上升清单,因为清单。 生成的检查表中的匹配是不必要的,您可以删除它们或防止它们如果您这样做。

要清楚,我对算法很感兴趣。 不要犹豫以任何语言上传代码,也不要像上传那样标准。

0
2019-05-03 22:39:05
资源 分享
答案: 5

在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);
}
0
2019-05-22 21:05:45
资源

您可以在python中使用2行执行此操作

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

这个模型的价格是n ^ 2(可能是集合的日志变量?),也是安排的s * log(s),其中s是集合的维数。

如果X = [1,2,4,...,2 ^ n],则该集的维数可以与n *(n-1)/ 2一样大。 因此,如果你打算创建这个核对表,那么在最糟糕的实例中肯定需要至少n ^ 2/2,因为这是结果的维度。

尽管如此,如果您打算选择结果的前k个分量,您可以在O(kn)中使用选项算法对Frederickson和Johnson(看到这里的血腥细节))排列的X + Y矩阵进行此操作。尽管可以将其更改为创建他们通过回收计算在线,并为此套装获得可靠的发电机。

@deuseldorf,Peter有一些复杂的问题(n!)我严重质疑deuseldorf建议“n factorial”但仅仅是“n,(真的很激动)!”

0
2019-05-19 23:22:04
资源

如果你正在寻求一种绝对语言不可知的补救措施,那么你肯定会在我的观点中严重失望,因为你将被困在for循环和一些条件。 尽管如此,如果你打开它大致有用的语言或有用的语言属性(我正在考虑你LINQ)之后我的同事可以在Ruby,Lisp,Erlang和其他人的同时加载这个带有经典实例的网页。

0
2019-05-07 19:59:41
资源

我能想到的理想是生成每组数量的矩阵,然后将这些行相互组合,a-la组合类型。 我似乎错过了一些直截了当的理解,肯定会披露更可靠的补救措施。

我的算法,在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)

我找到了一个小的翻新,一个对粗心的基于流的编码更敏感的翻新。 与成对组合列相反,同时组合它们中的每一个。 好处是您可以快速开始获取清单的组成部分。

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

尽管如此,如果你认识到你可能会使用每一个数量的蚊子,并且之前获得其中几个没有任何好处,请选择'foldl merge []',因为它要快得多。

0
2019-05-07 18:54:28
资源

而不是编码出来,我认为我会伪装成交响乐并且澄清我的推理,以确保更好的设计师可以在我的推理中抓住开口,如果必要的话。

在第一步,我们从数字大小为n的清单开始。 对于我们需要创建大小为n-1的核对表的每个号码,因为我们不包括自身的数字。 最后,我们有一份关于n个安排的清单的清单,这些清单是在O(n ^ 2)时间内创建的。

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由于故意排列清单(在安排的清单中每个组件添加一个数字,并且肯定还会安排清单)我们只能通过将每个清单相互组合来进行合并,而不是合并排序。整个很棒。 最终这需要花费O(n ^ 2)时间。

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

合并方法肯定会在定期合并操作之后进行检查,以确保没有重复数量。 由于任何人都可以寻求合并,我不会写出来。

所以这是我的补救措施。 整个算法的时间为O(n ^ 2)。 不要犹豫,提出任何错误或装修。

0
2019-05-07 17:31:57
资源