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

StackOverflow https://stackoverflow.com/questions/826

  •  08-06-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

Редактировать по состоянию на 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], тогда вам нужно только изучить верхние левые "углы" и выбрать самый нижний.

например ,

  • только 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

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

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

Другие советы

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

На первом шаге мы начинаем со списка чисел длиной 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) времени.Не стесняйтесь указывать на любые ошибки или улучшения.

Вы можете сделать это в двух строках на python с помощью

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

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

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

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

@deuseldorf, Питер Есть некоторая путаница с (n!) Я серьезно сомневаюсь, что deuseldorf имел в виду "n факториал", а просто "n, (очень взволнован)!"

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

Мой алгоритм на языке 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 []', так как это быстрее.

В 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);
}

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

Этот вопрос не дает мне покоя уже около суток.Потрясающе.

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top