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

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

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

3.08.2008 21:08:54
8 ОТВЕТОВ
РЕШЕНИЕ

Редактировать с 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

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

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

12
8.02.2018 21:40:29
Я думаю, что это O (n ^ 3), поскольку на каждом этапе есть n потенциальных «верхних левых углов».
user97370 5.02.2010 02:56:47
Вы можете реализовать этот алгоритм за O (n ^ 2 log n), сохранив первую невыбранную запись в каждой строке в очереди с приоритетами, но асимптотически это не лучше, чем просто генерация всех сумм и сортировка.
Reid Barton 3.10.2010 19:08:44
Если у вас есть два списка вместо одного, длиной m и n с m <n, то подход, основанный на k-способе слияния, дает O (mn log m), а не O (mn log (mn)). Кроме того, если m довольно мало (до нескольких сотен элементов, я бы предположил), подход, основанный на слиянии, будет намного лучше использовать кэш процессора (поскольку очередь с приоритетами или дерево слияния будут помещаться в кэш L1), что может легко повысить скорость в 100 и более раз, и, если она написана очень тщательно, можно эффективно использовать конвейер процессора, и в этом случае он должен действительно кричать.
dfeuer 25.08.2012 23:10:13
Если подумать 4 года спустя, это выглядит как действительно плохая версия сортировки слиянием :)
porges 6.09.2012 21:53:47

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

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

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

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

4
17.04.2015 10:17:10
Я думаю, что это O (N ^ 3), так как на каждом этапе в шаге 2 выполняется n сравнений
user97370 5.02.2010 02:56:20

Вы можете сделать это в две строки в 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, (очень взволнован)!»

2
11.08.2008 14:47:31
Это имеет лучшую сложность, чем все другие решения, я думаю! O (N ^ 2.log (п)). Это также самый читаемый и самый короткий.
user97370 5.02.2010 03:00:27

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

Мой алгоритм в 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 []», поскольку это быстрее.

1
6.08.2008 18:56:00
Я думаю (мой haskell ржавый), это O (N ^ 3), так как для каждой вещи в результате сделано O (n) сравнений.
user97370 5.02.2010 02:55:23

В 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);
}
1
8.08.2008 23:31:25

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

1
18.09.2008 22:15:18
Да, но для сортировки n ^ 2 вещей требуется O (n ^ 2 log n), поэтому сортировка никогда не доминирует.
user97370 5.02.2010 03:01:27

Этот вопрос мучает мой мозг уже около суток. Потрясающие.

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

1
3.07.2012 14:49:57

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

-4
3.08.2008 21:24:56