Эффективно получать отсортированные суммы из отсортированного списка
У вас есть возрастающий список чисел, который является наиболее эффективным алгоритмом, который вы можете придумать, чтобы получить возрастающий список сумм каждых двух чисел в этом списке. Дубликаты в результирующем списке не имеют значения, вы можете удалить их или избежать их, если хотите.
Чтобы было понятно, мне интересен алгоритм. Не стесняйтесь размещать код на любом языке и парадигме, которые вам нравятся.
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] - если у кого-то нет лучшего алгоритма для суммирования:)
Вместо того, чтобы кодировать это, я полагаю, что пошагово закодирую его и объясню свою логику, чтобы лучшие программисты могли пробить дыру в моей логике, если это необходимо.
На первом шаге мы начнем со списка чисел длиной 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) времени. Не стесняйтесь указывать на любые ошибки или улучшения.
Вы можете сделать это в две строки в 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, (очень взволнован)!"
В 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);
}
Лучшее, что я мог бы придумать, - это создать матрицу сумм каждой пары, а затем объединить строки, а-ля сортировка слиянием. Я чувствую, что мне не хватает некоторого простого понимания, которое покажет гораздо более эффективное решение.
Мой алгоритм в 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 []', как это быстрее.
Этот вопрос мучает мой мозг уже около суток. Потрясающие.
В любом случае, вы не можете легко уйти от природы 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 как хорошо, но это кажется возможным.
Независимо от того, что вы делаете, без дополнительных ограничений на входные значения, вы не можете сделать лучше, чем O(n^2), просто потому, что вам нужно перебирать все пары чисел. Итерация будет доминировать в сортировке (что вы можете сделать за O(n log n) или быстрее).
Если вы ищете действительно независимое от языка решение, то, на мой взгляд, вы будете сильно разочарованы, потому что застряли в цикле for и некоторых условных выражениях. Однако, если вы открыли его для функциональных языков или функций функциональных языков (я смотрю на вас LINQ), мои коллеги здесь могут заполнить эту страницу элегантными примерами на Ruby, Lisp, Erlang и других.