_{relacionados e inspirados por - Localizando partições sem soma}

Um conjunto Aé definido aqui como sendo claramente sem soma se

• 1) consiste em pelo menos três elementos |A| ≥ 3, e
• 2) sua auto-soma distinta A + A = { x + y | x, y in A}(com x,ydistintos, ie x≠y) não possui elementos em comum com A.

_{(Obsoleto -... Não use este vai para a frente esquerda aqui apenas porque algumas respostas podem tê-lo usado Ele não coincide com as condições acima Alternativamente, a equação x + y = znão tem solução para x,y,z ∈ A(novamente com x,y,zdistinta, ou seja, x≠y, x≠z, y≠z.) )}

Para um exemplo simples, {1,3,5}é claramente sem soma, mas {1,3,4}não é. {1,3}e {3}também não são, pois não têm pelo menos três elementos.

O desafio aqui é encontrar o maior subconjunto distintamente livre de soma da entrada fornecida.

Entrada

• Um conjunto não ordenado Ade números inteiros em qualquer formato conveniente .
• Os números inteiros podem ser positivos, negativos ou zero, mas pode-se presumir que cabem no [int]tipo de dados nativo do seu idioma (ou equivalente).
• É garantido que o conjunto tenha apenas elementos distintos (sem multisets aqui).
• O conjunto não é necessariamente classificado.

Resultado

• O maior subconjunto de A(que poderia ser Aele mesmo), que é distintamente sem soma. A saída pode estar em qualquer formato adequado.
• Se esse subconjunto não existir, envie um conjunto vazio ou outro valor falsey .
• Se vários subconjuntos estiverem vinculados ao maior, produza um ou todos eles.
• O subconjunto não precisa necessariamente ser classificado ou na mesma ordem que a entrada. Por exemplo, para {1,3,5}saída de entrada {5,1,3}é aceitável.

Regras adicionais

• As brechas padrão são proibidas.
• Isso é código-golfe , então todas as regras usuais de golfe se aplicam e o código mais curto vence.

Exemplos

Input     -> Output (any or all)
{0}       -> {}
{1, 2, 3} -> {}
{1, 3, 5} -> {1, 3, 5}
{1, 2, 3, 4, 5} -> {1, 2, 5}  {1, 2, 4}  {1, 3, 5}  {2, 3, 4}  {2, 4, 5}  {3, 4, 5}
{-5, 4, 3, -2, 0} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-5, 4, 3, -2} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-17, 22, -5, 13, 200, -1, 1, 9} -> {-17, 22, -5, 13, 200, -1, 1}  {-17, 22, -5, 200, -1, 1, 9}  {-17, -5, 13, 200, -1, 1, 9}

Geléia , 17 bytes

8BḊ+œc2S€f
ŒPÇÐḟṪ

Experimente online! ou verifique todos os casos de teste .

MATL , 47 43 bytes

nW:qB!ts2#Sw2>)PZ)"1G@)XJ2XN!"@sJ@X-m~*]?J.

Experimente online!

Explicação

Isso usa dois loops: um loop externo para gerar todos os subconjuntos possíveis e um loop interno para pegar todos os pares de elementos e ver se a soma é igual a qualquer outro elemento do subconjunto.

Subconjuntos de pelo menos três elementos são testados em ordem decrescente de elementos. O código para assim que um subconjunto válido é encontrado.

          % Take input implicitly
nW:q      % Generate [0 1 ... 2^n-1] where n is input length
B!        % Convert to binary. Gives a matrix. Each number corresponds to a column.
          % This will be used to select the elements of each subset
ts        % Duplicate. Sum of each column
2#S       % Sort. Output the sorted array and the indices of the sorting. Each index
          % corresponds to one possible subset
w2>       % Swap. Logical index of values that exceed 2. This is used to pick only
          % subsets of more than 2 elements
)         % Keeps only indices of subsets that have at least 3 elements
P         % Flip. This moves subsets with more elements to the front. As soon as a
          % subset fulfills the condition the outer loop will be exited, so we need
          % to start with the bigger subsets
Z)        % Index into columns of binary matrix. Each column is the binary pattern
          % defining a subset with at least 3 elements, starting with bigger subsets
"         % For each column. Each iteration corresponds to a subset
  1       %   Push 1
  G@)     %   Pick actual elements of each subset (logical index into input)
  XJ      %   Copy to clipboard J
  2XN!    %   All pairs of 2 elements from that subset. Each pair is a column
  "       %   For each column. Each iteration corresponds to a pair of elements
    @s    %     Sum of those two elements
    J@X-  %     Array with the other elements (obtained with set difference)
    m~    %     True if the sum of the two elemens is not a member of the array
    *     %     Multiply. Corresponds to logical AND
  ]       %   End for
  ?       %   If result is true: no sum of two elements equalled any element
    J     %     Push found subset (will be displayed implicitly)
    .     %     Exit loop
          %   End if implicitly
          % End for implicitly
          % Display stack implicitly

Python, 137 bytes

Uma abordagem ingênua. Faz um loop em todos os subconjuntos da entrada contendo pelo menos 3 valores, verificando a propriedade de cada um. Retorna []quando nenhum resultado é encontrado ou [S]se pelo menos um resultado é encontrado (onde Shá alguma tupla).

from itertools import*
lambda a:[c for n in range(3,len(a)+1)for c in combinations(a,n)if all(x+y-z for(x,y,z)in permutations(c,3))][-1:]

Javascript 246 263

a=>([...Array(1<<(l=a.length))].map((x,i)=>i.toString(2)).filter(n=>/1.*1.*1/.test(n)).map(s=>('0'.repeat(l)+s).slice(-l).replace(/./g,(b,p)=>+b&&o.push(a[p]),o=[])&&o).filter(u=>u.every((x,i)=>!u.some((y,j)=>j-i&&u.some((z,k)=>k-j&&!(z-x-y))))))

Até logo :( ... Mas foi uma boa codificação .. (eu acho)

Menos golfe:

f=a=>(
    [...Array(1<<(l=a.length))]
        .map((x,i)=>i.toString(2))
        .filter(n=>/1.*1.*1/.test(n))
        .map(s=>
            ('0'.repeat(l)+s).slice(-l).replace(/./g,
                (b,p)=>+b&&o.push(a[p])
            ,o=[])&&o
        )
        .filter(u=>
            u.every((x,i)=>
                !u.some((y,j)=>
                    j-i&&u.some((z,k)=>k-j&&!(z-x-y))
                )
            )
        )
)

document.body.innerHTML = JSON.stringify( f([1,2,3,4,5]), null, 1 );

Mathematica - 89 84 83 77 76 bytes

6 bytes salvos graças ao @ Sp3000

Provavelmente pode ser jogado muito mais, existe uma maneira mais curta de filtrar?

Select[Subsets@#,Length@#>2&&Intersection[#,Tr/@#~Subsets~{2}]=={}&]~Last~0&

Função anônima, retorna 0sem resposta.

Ruby, 107 bytes

Entrada é uma matriz. Coleta um subconjunto qualificado para cada tamanho de subconjunto 3até o tamanho da entrada e, em seguida, retorna o maior dentre os encontrados. Retorna nilse nenhum resultado for encontrado.

Devido à especificação conflitante, existem duas soluções que atualmente têm o mesmo número de conta.

Usando a primeira definição: ( { x + y | x, y ∈ A } ∩ A = ∅)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.combination(2).map{|a,b|a+b}&e==[]}}-[p])[-1]}

Usando a segunda definição ( ∀ x, y, z ∈ A: x + y ≠ z)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.permutation(3).all?{|a,b,c|a+b!=c}}}-[p])[-1]}

Pitão, 27 bytes

ef!f!*Fm-Fd.pYfqlY3yTfglT3y

Suíte de teste.