Eficientemente obter somas ordenadas de uma lista ordenada

votos
17

Você tem uma lista crescente de números, o que é o algoritmo mais eficiente que você pode pensar para obter a lista crescente de somas de cada dois números em que lista. Duplicatas na lista resultante são irrelevantes, você pode removê-los ou evitá-los se quiser.

Para ser claro, eu estou interessado no algoritmo. Sinta-se livre para postar o código em qualquer idioma e paradigma de que você gosta.

Publicado 03/08/2008 em 22:08
fonte usuário
Em outras línguas...                            


8 respostas

votos
12

Editar a partir de 2018: Você provavelmente deve parar de ler este. (Mas eu não posso excluí-lo como ele é aceito.)

Se você escrever as somas como este:

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ê vai notar que, desde M [i, j] <= M [i, j + 1] e M [i, j] <= M [i + 1, j], então você só precisa examinar a esquerda top " cantos" e escolher o menor.

por exemplo

  • apenas 1 canto superior esquerdo, 2 escolher
  • apenas 1, 5 escolher
  • 6 ou 8, 6 escolher
  • 7 ou 8, escolha sete
  • 9 ou 8, 8 escolher
  • 9 ou 9, escolher tanto :)
  • 10 ou 10 ou 10, escolher todos
  • 12 ou 11, 11 escolher
  • 12 ou 12, escolher tanto
  • 13 ou 13, escolher tanto
  • 14 ou 14, escolher tanto
  • 15 ou 16, 15 escolher
  • apenas 1, 16 escolher
  • apenas 1, 17 escolher
  • apenas 1, 18 escolher

Claro que, quando você tem lotes de cantos superiores esquerdo, em seguida, esta solução recai.

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

Respondeu 18/09/2008 em 22:41
fonte usuário

votos
4

Ao invés de codificação isso, eu acho que eu vou pseudo-código-lo em etapas e explicar a minha lógica, para que melhores programadores podem criar buracos em minha lógica, se necessário.

No primeiro passo, começar com uma lista de números de comprimento n. Para cada número, precisamos criar uma lista de comprimento n-1 becuase não está adicionando um número para si. No final, temos uma lista de cerca de n listas ordenadas que foi gerada em O (n ^ 2) tempo.

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, porque as listas foram classificadas por design (adicionar um número a cada elemento em uma lista ordenada ea lista ainda serão ordenados) nós simplesmente pode fazer um mergesort fundindo cada lista juntos em vez de mergesorting todo o lote. No final, este deve ter 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 fusão seria então o passo normal de fusão com um cheque para certificar-se de que não existem somas duplicados. Eu não vou escrever isso porque qualquer um pode olhar para cima mergesort.

Portanto, não é a minha solução. O algoritmo inteiro é O tempo (n ^ 2). Sinta-se livre para apontar eventuais erros ou melhorias.

Respondeu 04/08/2008 em 00:06
fonte usuário

votos
2

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 deste é n ^ 2 (talvez um factor de registo adicional para o conjunto?) Para o registo de iteração e s * (s) para a triagem onde s é o tamanho do conjunto.

O tamanho do conjunto podia ser tão grande quanto n * (n-1) / 2, por exemplo, se X = [1,2,4, ..., 2 ^ n]. Então, se você deseja gerar esta lista que vai demorar pelo menos n ^ 2/2 no pior caso uma vez que este é o tamanho da saída.

No entanto, se você quiser selecionar os primeiros k elementos do resultado você pode fazer isso em O (kn) usando um algoritmo de seleção para ordenados matrizes X + Y por Frederickson e Johnson ( ver aqui para detalhes sangrentos) . Embora isso provavelmente pode ser modificado para gerá-los on-line através da reutilização de computação e obter um gerador eficiente para este conjunto.

@deuseldorf, Peter Existe alguma confusão sobre (n!) Eu duvido seriamente deuseldorf significava "n factorial", mas simplesmente "n, (muito animado)!"

Respondeu 11/08/2008 em 15:47
fonte usuário

votos
1

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

Respondeu 18/09/2008 em 23:15
fonte usuário

votos
1

Esta questão tem sido forçando meu cérebro por cerca de um dia agora. Impressionante.

De qualquer forma, você não pode fugir do n ^ 2 natureza do-lo facilmente, mas você pode fazer um pouco melhor com a fusão desde que você pode obrigado a gama de inserir cada elemento.

Se você olhar para todas as listas que você gerar, eles têm a seguinte forma:

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

Se você virar 90 graus, você obtém:

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

Agora, o processo de integração deve ser tomada duas listas ie i+1(que correspondem às listas em que o primeiro membro é sempre a[i]e a[i+1]), você pode obrigado a gama de inserir elementos (a[i + 1], a[j])na lista ipela localização (a[i], a[j])e da localização (a[i + 1], a[j + 1]).

Isso significa que você deve se fundir em sentido inverso em termos de j. Eu não sei (ainda) se você pode alavancar esse outro lado jtambém, mas parece possível.

Respondeu 21/08/2008 em 19:16
fonte usuário

votos
1

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);
}
Respondeu 09/08/2008 em 00:05
fonte usuário

votos
1

O melhor que eu poderia vir acima com é produzir uma matriz de soma de cada par, e em seguida, mesclar as linhas juntas, a-la merge sort. Eu sinto como se estivesse faltando alguma introspecção simples que irá revelar uma solução muito mais eficiente.

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

Eu encontrei uma pequena melhoria, que é mais passível de codificação baseado em fluxo de preguiçoso. Em vez de juntar as colunas de pares, fundir todos eles de uma vez. A vantagem é que você começa a receber 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 está indo para usar todas as somas, e não há nenhuma vantagem para a obtenção de alguns deles mais cedo, ir com ' foldl merge []', como é mais rápido.

Respondeu 03/08/2008 em 22:36
fonte usuário

votos
-4

Se você está procurando uma solução agnóstica verdadeiramente a linguagem, então você será muito desapontados na minha opinião, porque você vai ser preso com um loop for e algumas condicionais. No entanto, se você abri-lo para linguagens funcionais ou recursos de linguagem funcional (estou olhando para você LINQ), então meus colegas aqui pode encher esta página com exemplos elegantes em Ruby, Lisp, Erlang, e outros.

Respondeu 03/08/2008 em 22:24
fonte usuário

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