Эффективно получать отсортированные суммы из отсортированного списка

Question

У вас есть возрастающий список чисел, который является наиболее эффективным алгоритмом, который вы можете придумать, чтобы получить восходящий список сумм каждых двух чисел в этом списке. Дубликаты в результирующем списке не имеют значения, вы можете удалить их или избежать их, если хотите.

Чтобы было понятно, мне интересен алгоритм. Не стесняйтесь размещать код на любом языке и парадигме, которые вам нравятся.

Answer 1

Редактировать с 2018 года: Вам, вероятно, следует перестать читать это. (Но я не могу удалить его, как это принято.)

Если вы выписываете суммы следующим образом:

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

Вы заметите, что, поскольку M [i, j] <= M [i, j + 1] и M [i, j] <= M [i + 1, j], то вам нужно только изучить в верхнем левом углу и выберите самый нижний. </p>

, например

• только 1 верхний левый угол, выберите 2
• только 1, выбор 5
• 6 или 8, выберите 6
• 7 или 8, выберите 7
• 9 или 8, выберите 8
• 9 или 9, выберите оба:)
• 10 или 10 или 10, выбрать все
• 12 или 11, выберите 11
• 12 или 12, выберите оба
• 13 или 13, выберите оба
• 14 или 14, выберите оба
• 15 или 16, выберите 15
• только 1, выбор 16
• только 1, выбор 17
• только 1, выберите 18

Конечно, когда у вас есть лоты верхних левых углов, тогда это решение переходит в *. 1044 *

Я почти уверен, что эта проблема Ω (n²), потому что вы должны вычислять суммы для каждого M [i, j] - если у кого-то нет лучшего алгоритма суммирования:)

Answer 2

Вместо того, чтобы кодировать это, я полагаю, что пошагово закодирую его и объясню свою логику, чтобы лучшие программисты могли пробить мою логику, если это необходимо.

На первом шаге мы начинаем со списка чисел длиной 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 

На шаге 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

Тогда метод слияния будет обычным шагом слияния с проверкой на отсутствие дублирующихся сумм. Я не буду это выписывать, потому что любой может посмотреть mergesort.

Так что есть мое решение. Весь алгоритм O (n ^ 2) времени. Не стесняйтесь указывать на любые ошибки или улучшения.

Answer 3

Вы можете сделать это в две строки в Python с помощью

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

Стоимость этого составляет n ^ 2 (может быть, дополнительный логарифмический коэффициент для набора?) Для итерации и s * log (s) для сортировки, где s - размер набора.

Размер набора может быть таким же большим, как n * (n-1) / 2, например, если X = [1,2,4, ..., 2 ^ n]. Поэтому, если вы хотите сгенерировать этот список, в худшем случае потребуется как минимум n ^ 2/2, так как это размер вывода.

Однако, если вы хотите выбрать первые k элементов результата, вы можете сделать это в O (kn), используя алгоритм выбора отсортированных матриц X + Y по Фредериксону и Джонсону ( см. Здесь подробности) . Хотя это, вероятно, можно изменить, чтобы генерировать их онлайн, повторно используя вычисления и получая эффективный генератор для этого набора.

@ deuseldorf, Peter Существует некоторая путаница в отношении (n!) Я серьезно сомневаюсь, что deuseldorf означало «n factorial», но просто «n, (очень взволнован)!»

Answer 4

Независимо от того, что вы делаете, без дополнительных ограничений на входные значения, вы не можете сделать лучше, чем O (n ^ 2), просто потому, что вам нужно перебирать все пары чисел. Итерация будет доминировать в сортировке (что вы можете сделать за O (n log n) или быстрее).

Answer 5

Этот вопрос мучает мой мозг уже около суток. Высокий.

В любом случае, вы не можете легко уйти от природы n ^ 2, но вы можете сделать немного лучше с помощью слияния, так как вы можете ограничить диапазон для вставки каждого элемента.

Если вы посмотрите на все списки, которые вы генерируете, они имеют следующую форму:

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

Если перевернуть его на 90 градусов, вы получите:

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

Теперь процесс слияния должен принимать два списка i и i+1 (которые соответствуют спискам, где первый член всегда a[i] и a[i+1]), вы можете ограничить диапазон для вставки элемента (a[i + 1], a[j]) в список i по местоположению (a[i], a[j]) и местоположению (a[i + 1], a[j + 1]).

Это означает, что вы должны слить в обратном порядке в терминах j. Я не знаю (пока), можете ли вы использовать это и для j, но это кажется возможным.

Answer 6

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

Лучшее, что я мог бы придумать, - это создать матрицу сумм каждой пары, а затем объединить строки, а-ля сортировка слиянием. Я чувствую, что мне не хватает некоторого простого понимания, которое покажет гораздо более эффективное решение.

Мой алгоритм, на Хаскеле:

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 []', поскольку это быстрее.

Answer 8

Если вы ищете действительно независимое от языка решение, то, на мой взгляд, вы будете сильно разочарованы, потому что застряли в цикле for и некоторых условных выражениях. Однако, если вы открыли его для функциональных языков или функций функциональных языков (я смотрю на вас LINQ), мои коллеги здесь могут заполнить эту страницу элегантными примерами на Ruby, Lisp, Erlang и других.