_{relacionado e inspirado por - Encontrar particiones sin suma}

Un conjunto Ase define aquí como claramente sin suma si

• 1) consta de al menos tres elementos |A| ≥ 3, y
• 2) su auto-suma distinta A + A = { x + y | x, y in A}(con x,ydistinta, es decir, x≠y) no tiene elementos en común con A.

_{(Obsoleto -... No utilice este ir hacia delante a la izquierda aquí sólo porque algunas respuestas pueden haber usado No coincide con las condiciones anteriores Alternativamente, la ecuación x + y = zno tiene solución de x,y,z ∈ A(de nuevo con x,y,zdistinto, es decir, x≠y, x≠z, y≠z.) )}

Por un simple ejemplo, {1,3,5}es claramente libre de sumas, pero {1,3,4}no lo es. {1,3}y {3}tampoco lo son, ya que no son al menos tres elementos.

El desafío aquí es encontrar el subconjunto más grande sin suma de la entrada dada.

Entrada

• Un conjunto desordenado Ade enteros en cualquier formato conveniente .
• Los enteros pueden ser positivos, negativos o cero, pero se puede suponer que encajan en el [int]tipo de datos nativo de su idioma (o equivalente).
• Se garantiza que el conjunto solo tiene elementos distintos (no hay multisets aquí).
• El conjunto no está necesariamente ordenado.

Salida

• El subconjunto más grande de A(que podría ser él Amismo), que es claramente libre de sumas. La salida puede estar en cualquier formato adecuado.
• Si no existe tal subconjunto, envíe un conjunto vacío u otro valor falsey .
• Si varios subconjuntos están vinculados para el más grande, genere uno o todos ellos.
• El subconjunto no necesita necesariamente ser ordenado, o en el mismo orden que la entrada. Por ejemplo, para entrada, {1,3,5}salida {5,1,3}es aceptable.

Reglas Adicionales

• Las lagunas estándar están prohibidas.
• Este es el código de golf , por lo que se aplican todas las reglas habituales de golf, y gana el código más corto.

Ejemplos

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}

Jalea , 17 bytes

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

Pruébalo en línea! o verificar todos los casos de prueba .

MATL , 47 43 bytes

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

Pruébalo en línea!

Explicación

Utiliza dos bucles: un bucle externo para generar todos los subconjuntos posibles y un bucle interno para tomar todos los pares de elementos y ver si la suma es igual a cualquier otro elemento del subconjunto.

Los subconjuntos de al menos 3 elementos se prueban en orden decreciente de elementos. El código se detiene tan pronto como se encuentre un subconjunto válido.

          % 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

Un enfoque ingenuo. Recorre todos los subconjuntos de la entrada que contienen al menos 3 valores, verificando la propiedad para cada uno. Devuelve []cuando no se encuentra ningún resultado o [S]si se encuentra al menos un resultado (donde Shay alguna 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))))))

Hasta luego :( ... Pero fue una buena codificación ... (creo)

Menos golfizado:

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 guardados gracias a @ Sp3000

Probablemente se pueda jugar mucho más al golf, ¿hay alguna forma más corta de filtrar?

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

Función anónima, devuelve 0sin respuesta.

Ruby, 107 bytes

La entrada es una matriz. Recopila un subconjunto calificado para cada tamaño de subconjunto desde 3la longitud de entrada, luego devuelve el más grande de los encontrados. Devuelve nilsi no se encuentra ningún resultado.

Debido a las especificaciones en conflicto, hay dos soluciones que actualmente tienen el mismo bytecount.

Usando la primera definición: ( { 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 la segunda definición ( ∀ 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]}

Pyth, 27 bytes

ef!f!*Fm-Fd.pYfqlY3yTfglT3y

Banco de pruebas.