Algoritmo eficiente para 'cancelar a soma' de um conjunto de somas

24

Dado um conjunto múltiplo de números naturais X, considere o conjunto de todas as somas possíveis:

sums(X)={iAi|AX}

Por exemplo, sums({1,5})={0,1,5,6} enquanto sums({1,1})={0,1,2} .

Qual é o algoritmo mais eficiente para calcular a operação inversa (medida em termos do tamanho do conjunto de somas de entrada)? Especificamente, é possível calcular com eficiência qualquer um dos seguintes itens:

  1. Se um determinado conjunto é um conjunto válido de somas. (Por exemplo, {0,1,2} é válido, mas {0,1,3} não é.)
  2. Um multiset que soma ao conjunto fornecido.
  3. O menor conjunto múltiplo que soma ao conjunto especificado. (Por exemplo, {1,2} e {1,1,1} ambos somam {0,1,2,3} mas o primeiro é menor.)
Uri Granta
fonte
1
Você poderia nos fornecer o conjunto múltiplo de somas, e não o conjunto de somas? Isso criaria uma simetria agradável (visto que você começa com um conjunto múltiplo de valores).
DW
1
Outra pergunta - você está mais interessado em resultados teóricos (por exemplo, complexidade assintótica) ou soluções práticas (esquemas que podem funcionar bem na prática)? Neste último caso, você tem uma idéia de valores típicos para parâmetros: por exemplo, o tamanho do multiset X, o tamanho do maior elemento no multiset X, a maior multiplicidade? Isso pode afetar se é razoável aplicar um "grande martelo", como um solucionador de ILP ou SAT.
DW
@ DW Estou definitivamente interessado em usar o conjunto de somas em vez do multiset (embora isso possa ser um problema interessante também). Além disso, esse era originalmente um problema matemático recreativo, por isso estou mais interessado nos limites da complexidade do que em uma solução prática.
Uri Granta
3
Se você receber o conjunto múltiplo de somas, é bastante simples fazer isso com avidez (veja, por exemplo, math.stackexchange.com/questions/201545/… ).
Jschnei
@UriZarfaty o conjunto dado como entrada já está classificado? Finalmente, isso é definido ou multiset? O comentário ainda sugere que você deseja um conjunto puro.
Mal

Respostas:

9

Solução

A solução tem duas partes. Primeiro descobrimos o conjunto mínimo e depois provamos que ele pode representar o conjunto da soma de potência. A solução é ajustada para implementação de programação.

Algoritmo de conjunto mínimo

  1. Encontre o elemento máximo do conjunto da soma (multi). P , o conjunto mínimo potencial (multi) está inicialmente vazio.amP

  2. A menos que haja apenas um grupo, representam de todas as maneiras possíveis como um par de montantes que se somam a um m , S i j = { ( um i , um j ) | a i + a j = a m }amamSij={(ai,aj)|ai+aj=am}

  3. Verifique se todos os elementos do conjunto de somas estão incluídos.

  4. Encontre o elemento máximo de todos os S i j (ou seja, juntos) com a seguinte propriedade: para cada S i j , a s está em S i j , ou podemos encontrar um p do conjunto de somas para que um p + a s está em S i j .asSijSijasSijapap+asSij

  5. Se não contiver a s , apenas a soma a s + a p , remova a p + a s de S i j (ou marque apenas uma marca para ignorá-la) e insira a p e a s em S i j .Sijasas+apap+asSijapasSij

  6. Se um elemento está presente em cada removê-lo de todo S i j uma vez (ou apenas definir uma marca de ignorá-lo e não tocá-lo por mais tempo) e adicioná-lo à lista de elementos de potencial mínimo set P .SijSijP

  7. Repita até que todos os estejam vaziosSij

  8. Se parte de permanecer vazia e não pudermos continuar, tente novamente com o valor máximo de todas as S i j .SijSij

  9. Recriar os passos recursiva sem remoções e continuar com o algoritmo de cobertura set poder sobre . (Antes disso, você pode fazer uma verificação segura de que P inclui todos os elementos que não podem ser representados como uma soma de dois elementos, portanto, eles devem estar no conjunto subjacente, com certeza. Por exemplo, o elemento mínimo deve estar em P. )PPP

(10. Observe que uma solução de conjunto mínima, que é o objetivo do algoritmo, não pode conter mais de uma repetição do mesmo número.)

Exemplo:

{2,3,5,7,8,10,12,13,15}

Represente 15 de todas as maneiras possíveis como uma soma de dois números do conjunto de somas.

(13,2),(12,3),(10,5),(8,7)

Tente encontrar o número máximo que está em todos os grupos ou que pode ser representado como uma soma. Obviamente, podemos começar a procurá-lo a partir das 8, não faz sentido ir além.

13 do primeiro grupo é 13 = 8 + 5, então 13 é bom, mas 12 do segundo grupo não é bom, pois não há 4 para fazer 12 = 8 + 4 no conjunto de somas. Em seguida, tentamos com 7. Mas imediatamente 13 não podem ser cobertos, não há 6.

Em seguida, tentamos 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, e nos últimos 8 = 5 + 3 ou 7 = 5 + 2, mas não ambos. Os grupos são agora:

((5,8),2),((5,7),3),((5,5),5),((5,3),7)

5 está repetindo em todos os grupos, portanto, extraímos . Extraímos 5 apenas uma vez de cada grupo.P={5}

(8,2),(7,3),(5,5),(3,7)

Obviamente, não há sentido em ir além de 5, então tentamos 5 novamente. 8 = 5 + 3, 7 = 5 + 2, então está tudo bem

((5,3),2),((5,2),3),(5,5),(3,(5,2))

Extraia um 5 novamente de todos os grupos, pois está repetindo. (Isso não é comum, mas nosso caso é deliberadamente criado para mostrar o que fazer caso tenhamos repetições.) P={5,5}

(3,2),(2,3),(5),(3,2)

Agora tentamos com 3 e temos 5 = 3 + 2. Adicione-o ao grupo.

(3,2),(2,3),(3,2),(3,2)

Agora extraia 3 e 2, pois eles estão repetindo em todos os lugares e estamos bem e os grupos estão vazios.P={5,5,3,2}

(),(),(),()

Agora, precisamos recriar passos recursiva sem remoções, isto significa simplesmente fazer o acima sem realmente remover os elementos de apenas colocando-os em P e marcação não para alterá-lo por mais tempo.SijP

( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) , 7

(13,2),(12,3),(10,5),(8,7)
( ( 5 , ( 5 , 3 ) ) , 2 ) , ( ( 5 , ( 5 , 2 ) )) , 3 ) , ( ( 5 , ( 3 , 2 ) ) , 5 ) , ( ( 5 , 3 ) , ( 5 , 2 ) )
((5,8),2),((5,7),3),((5,5),5),((5,3),7)
((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))

Cobertura do conjunto de potência

O objetivo desta parte é verificar se o conjunto mínimo encontrado é capaz de cobrir o conjunto de soma de potência. É possível que uma solução encontrada possa cobrir todas as somas fornecidas, mas elas não são somas de conjunto de potência. (Tecnicamente, você pode simplesmente criar um conjunto de soma de potência a partir do conjunto mínimo encontrado e verificar se cada soma, como dita o conjunto de potência, está no conjunto de soma inicial. Isso é tudo que acabou de ser mesclado com o que já temos, para que nada seja desperdiçado. Você pode fazer esta parte enquanto rebobina a recursão.)

  1. Codifique todos os elementos do conjunto mínimo usando potências sucessivas de 2. A ordem não é importante. Codifique o mesmo elemento com um novo valor quantas vezes estiver repetindo. Comece com C = 1, cada elemento seguinte tem C = 2C.

(2=[1],3=[2],5=[4],5=[8])
  1. Substitua os elementos na lista de recursão restaurada,

((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))

com a codificação: 2 com 1, 3 com 2, 5 com 4 e outro 5 com 8. Observe que cada elemento tem codificação diferente, mesmo que sejam repetidos.

((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))
  1. Colete todas as somas intermediárias, no momento em que temos (1,2,4,8)

((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))

(1,2,3,4,5,8,9,10)

((14),1),((13),2),((7),8),(15)

(1,2,3,4,5,8,9,10,13,14,15)

{(15),(15),(15),(15)}
  1. 2m1mm=4

  2. 12m1

(6,7,11,12)

  1. Justifique sua ausência da seguinte maneira: represente cada número em forma binária

(6=01102) (7=01112) (11=10112) (12=10102)

601102(2=[1],3=[2],5=[4],5=[8]){2,3,5,7,8,10,12,13,15}, então está tudo bem.

701112(2=[1],3=[2],5=[4],5=[8])

1112

Se qualquer representação binária corresponder à soma que não puder ser encontrada, relate que não há solução.

(2,3,5,5)

Discussão

Era necessário fornecer o algoritmo que verifica se as somas cobrem a conclusão do conjunto de potência, que é o que está oculto na expansão binária. Por exemplo, se excluirmos 8 e 7 do exemplo inicial, a primeira parte ainda forneceria a solução, apenas a segunda parte relataria combinações ausentes de somas.

mnlog(m)mlog2(m)mnlog(m)

mlogmmlog2(m)

mlog3(m)

Partes do algoritmo assumem que podemos encontrar o par de somas em tempo linear e isso requer classificação.

Início incorreto

2,3,4,5,6,7,8,9,10,11,12,13,152,3,4,6Sij

5,4,3,3

2,2,3,4,42,3,4,6

O objetivo deste algoritmo é fornecer uma solução depois de iniciar tudo corretamente.

Melhorias

O passo 4. é aquele que pode ser atualizado dessa maneira: em vez de máximo, poderíamos experimentar todos os elementos em ordem decrescente que satisfaçam a condição especificada. Criamos um ramo separado para cada um. Se algum ramo não der uma solução, cancele-o.

2,3,4,5,6,7,8,9,10,11,12,13,157,6,5,4de maneiras separadas, pois todos eles estão passando no primeiro teste. (Não há razão para usar 2 ou 3, pois sabemos que eles precisam estar no conjunto subjacente.) E simplesmente continue assim até coletarmos todas as versões que podem chegar ao fim. Isso criaria uma solução de cobertura total que descobriria mais de um conjunto subjacente.

Outra coisa, como sabemos que não podemos ter mais de uma repetição se o caso for mínimo, podemos incorporar isso em nosso algoritmo.

No geral, a condição na etapa 4. de que um número deve se repetir em todos os grupos ou ter capacidade de criar uma soma é forte o suficiente para nos tirar das águas exponenciais diretas, o que seria um algoritmo de simplesmente experimentar todas as combinações e criar o poder definido sobre cada um até encontrarmos uma correspondência.


fonte
1
Mais amplamente: vejo uma descrição textual de um algoritmo, mas (a) nenhum pseudocódigo e (b) nenhuma prova de correção. Por que você acha que essa abordagem fornece um algoritmo que funcionará corretamente em todas as entradas possíveis? Qual a justificativa? Você tem uma prova de correção para isso?
DW
Acho que o problema levou cerca de 30 horas de trabalho todos juntos (taxa horária de 30 vezes, bem ...). Mas não há opção paga.
Por fim, leia a resposta nos detalhes que merecia. Ótimo trabalho!
Uri Granta
1

NOTA: Isso não funciona muito bem em geral, veja o contra-exemplo de Uri abaixo.

YY

  • 0Y
  • yYyXY
  • Deixei z1<<znYYY=Y+{0,y}0Yi=1,,nzi+yYziYziyYzi+yYzi+yYziY
  • Yy,y,

1yO(n)O(n2)

Y={0,1,3,4,5,6,7}{0,1,3,4,6}{0,1,3,5,6}yY{a+ky}YY

Klaus Draeger
fonte
É óbvio que Y 'não leva a um beco sem saída? Afinal, pode haver muitos Y's tais que Y = Y '+ {0, y}. Por exemplo {0,1,2,3,4} = {0,2,3} + {0,1} = {0,1,2,3} + {0,1}, mas a decomposição anterior leva a uma fim da linha.
Uri Granta
Isso é verdade e é um problema real. Vou ter que ver se pode ser consertado. Obrigado!
Klaus Draeger
YkY=Y+{0,y,,y}{0,y,,y}kyY