Obtenha com eficiência somas ordenadas de uma lista ordenada

08-06-2019
|

Pergunta

Você tem uma lista crescente de números, qual é o algoritmo mais eficiente que você pode imaginar para obter a lista crescente de somas de cada dois números nessa lista.As duplicatas na lista resultante são irrelevantes; você pode removê-las ou evitá-las, se desejar.

Para ser claro, estou interessado no algoritmo.Sinta-se à vontade para postar código em qualquer linguagem e paradigma que desejar.

Solução

Editar a partir de 2018:Você provavelmente deveria parar de ler isso.(Mas não posso excluí-lo porque é aceito.)

Se você escrever as somas assim:

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

Você notará que como M[i,j] <= M[i,j+1] e M[i,j] <= M[i+1,j], então você só precisa examinar o canto superior esquerdo " cantos" e escolha o mais baixo.

por exemplo.

apenas 1 canto superior esquerdo, escolha 2
apenas 1, escolha 5
6 ou 8, escolha 6
7 ou 8, escolha 7
9 ou 8, escolha 8
9 ou 9, escolha os dois :)
10 ou 10 ou 10, escolha todos
12 ou 11, escolha 11
12 ou 12, escolha ambos
13 ou 13, escolha ambos
14 ou 14, escolha ambos
15 ou 16, escolha 15
apenas 1, escolha 16
apenas 1, escolha 17
apenas 1, escolha 18

Claro, quando você tem grande quantidade dos cantos superiores esquerdos, então esta solução é devolvida.

Tenho quase certeza de que esse problema é Ω(n²), porque você precisa calcular as somas para cada M[i,j] - a menos que alguém tenha um algoritmo melhor para o somatório :)

Outras dicas

Em vez de codificar isso, vou pseudocodificá-lo em etapas e explicar minha lógica, para que programadores melhores possam abrir buracos em minha lógica, se necessário.

Na primeira etapa começamos com uma lista de números de comprimento n.Para cada número precisamos criar uma lista de comprimento n-1 porque não estamos adicionando um número a si mesmo.No final, temos uma lista de cerca de n listas ordenadas que foram geradas em tempo 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

Na etapa 2, como as listas foram classificadas por design (adicione um número a cada elemento em uma lista classificada e a lista ainda será classificada), podemos simplesmente fazer um mergesort mesclando cada lista em vez de mesclar todo o lote.No final, isso deve levar tempo 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 método de mesclagem seria então a etapa normal de mesclagem com uma verificação para garantir que não haja somas duplicadas.Não vou escrever isso porque qualquer um pode procurar o mergesort.

Então aí está minha solução.Todo o algoritmo é de tempo O (n ^ 2).Sinta-se à vontade para apontar quaisquer erros ou melhorias.

Você pode fazer isso em duas linhas em python com

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

O custo disso é n ^ 2 (talvez um fator de log extra para o conjunto?) Para a iteração e s * log(s) para a classificação, onde s é o tamanho do conjunto.

O tamanho do conjunto pode ser tão grande quanto n*(n-1)/2, por exemplo, se X = [1,2,4,...,2^n].Portanto, se você quiser gerar esta lista, será necessário pelo menos n ^ 2/2 na pior das hipóteses, pois esse é o tamanho da saída.

No entanto, se você quiser selecionar os primeiros k elementos do resultado, poderá fazer isso em O(kn) usando um algoritmo de seleção para matrizes X+Y ordenadas de Frederickson e Johnson (veja aqui para detalhes sangrentos).Embora isso provavelmente possa ser modificado para gerá-los online, reutilizando a computação e obtendo um gerador eficiente para este conjunto.

@DeuselDorf, Peter Há alguma confusão sobre (n!) Eu duvido seriamente deuseldorf significava "natorial", mas simplesmente "n, (muito animado)!"

O melhor que consegui é produzir uma matriz de somas de cada par e, em seguida, mesclar as linhas, como a classificação por mesclagem.Sinto que estou perdendo alguns insights simples que revelarão uma solução muito mais eficiente.

Meu algoritmo, em 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)

Encontrei uma pequena melhoria, mais adequada à codificação lenta baseada em fluxo.Em vez de mesclar as colunas em pares, mescle todas elas de uma vez.A vantagem é que você começa a obter os elementos da lista imediatamente.

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

No entanto, se você sabe que usará todas as somas e não há vantagem em obter algumas delas mais cedo, escolha 'foldl merge []', pois é mais rápido.

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

Não importa o que você faça, sem restrições adicionais nos valores de entrada, você não pode fazer melhor do que O(n^2), simplesmente porque precisa iterar por todos os pares de números.A iteração dominará a classificação (o que você pode fazer em O(n log n) ou mais rápido).

Esta questão está destruindo meu cérebro há cerca de um dia.Incrível.

De qualquer forma, você não pode fugir facilmente da natureza n ^ 2, mas pode fazer um pouco melhor com a mesclagem, pois pode limitar o intervalo para inserir cada elemento.

Se você observar todas as listas que você gera, elas terão o seguinte formato:

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

Se você girar 90 graus, obterá:

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

Agora, o processo de mesclagem deve incluir duas listas i e i+1 (que correspondem a listas onde o primeiro membro é sempre a[i] e a[i+1]), você pode vincular o intervalo para inserir o elemento (a[i + 1], a[j]) na lista i pela localização de (a[i], a[j]) e a localização de (a[i + 1], a[j + 1]).

Isso significa que você deve mesclar ao contrário em termos de j.Não sei (ainda) se você pode aproveitar isso j também, mas parece possível.

Se você está procurando uma solução verdadeiramente independente de linguagem, ficará muito desapontado, na minha opinião, porque ficará preso a um loop for e algumas condicionais.No entanto, se você abriu para linguagens funcionais ou recursos de linguagem funcional (estou olhando para você LINQ), então meus colegas aqui podem preencher esta página com exemplos elegantes em Ruby, Lisp, Erlang e outros.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow