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

голоса
17

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

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

Задан 03/08/2008 в 22:08
источник пользователем
На других языках...                            


8 ответов

голоса
12

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

например

  • только один верхний левый угол, выбрать 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] - если кто-то имеет лучший алгоритм для суммирования :)

Ответил 18/09/2008 d 22:41
источник пользователем

голоса
4

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

На первом этапе мы начинаем со списком длиной числа п. Для каждого номера мы должны создать список длины п-1 becuase мы не добавляем число к себе. К концу у нас есть список около п отсортированных списков, который был создан в О времени (п ^ 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, так как списки были отсортированы по дизайну (добавить номер к каждому элементу в отсортированном списке и список по-прежнему будет отсортирован) мы можем просто сделать слияние путем объединения каждого список вместе, а не mergesorting всей партии. В конце концов это должно занять время 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) время. Не стесняйтесь указать любые ошибки или улучшение.

Ответил 04/08/2008 d 00:06
источник пользователем

голоса
2

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

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

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

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

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

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

Ответил 11/08/2008 d 15:47
источник пользователем

голоса
1

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

Ответил 18/09/2008 d 23:15
источник пользователем

голоса
1

Этот вопрос был нарушающие покой моего мозга в течение приблизительно дня на день. Потрясающие.

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

Ответил 21/08/2008 d 19:16
источник пользователем

голоса
1

В 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);
}
Ответил 09/08/2008 d 00:05
источник пользователем

голоса
1

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

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

Ответил 03/08/2008 d 22:36
источник пользователем

голоса
-4

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

Ответил 03/08/2008 d 22:24
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more