Un ensemble est sans somme s'il n'y a pas deux éléments (pas nécessairement distincts) lorsqu'ils sont ajoutés ensemble font partie de l'ensemble lui-même.

Par exemple, {1, 5, 7}est sans somme, car tous les membres sont impairs, et deux nombres impairs lorsqu'ils sont additionnés sont toujours pairs. En revanche, {2, 4, 9, 13}n'est pas sans somme, que ce soit 2 + 2 = 4ou 4 + 9 = 13additionner à un membre de l'ensemble.

Écrivez un programme ou une fonction qui prend un ensemble en entrée et génère une valeur Truthy si l'ensemble est sans somme, et Falsy sinon.

Exemples:

Sum-free:
{}
{4}
{1, 5, 7}
{16, 1, 4, 9}

Not sum-free:
{0}
{1, 4, 5, 7}
{3, 0}
{16, 1, 4, 8}

Pyth - 8 5 octets

Merci à @FryAmTheEggman de m'avoir sauvé 3 octets.

!@sM*

Suite de test .

!             Logical not. This makes the empty intersection true and vice versa.
 @    Q       Setwise intersection with input (implictly).
  sM          Map sum to all the pairs.
   *QQ        Get all pairs by doing cartesian product with input*input (implicit).

Python 2, 41 octets

lambda s:s==s-{a+b for a in s for b in s}

s devrait être un ensemble Python.

Fait amusant: sum-freeest une anagramme de mon nom.

Gelée , 5 octets

ṗ3ḅ-P

Essayez-le en ligne!

Comment ça marche

ṗ3ḅ-P  Main link. Argument: A (array)

ṗ3     Take the third Cartesian power of A, i.e., generate all triplets that
       consist of elements of A.
  ḅ-   Convert each triplet from base -1 to integer.
       This maps [a, b, c] to a - b + c = (a + c) - b.
       If (a + c) belong to A, this will yield 0 for some b.
    P  Take the product of all resulting integers. 

JavaScript, 86 42 41 octets

n=>!n.some(m=>n.some(o=>n.includes(m+o)))

Merci Cᴏɴᴏʀ O'Bʀɪᴇɴ de m'avoir sauvé une tonne d'octets entre parenthèses / accolades. Merci également à Neil d'avoir souligné que la fonction renvoyait la valeur booléenne opposée à ce qu'elle aurait dû.

J'ai essayé de réduire les octets en redéfinissant n.somemais cela ne fonctionne pas car c'est malheureusement une fonction prototype. Il pourrait y avoir une meilleure solution avec Array.prototype.mapJS, mais la fonction some est vraiment amusante.

Je me demande maintenant s'il existe un moyen plus court que d' .includesutiliser quelque chose comme .indexOf et d'ajouter 1 (ce qui lui donnerait une valeur vraie s'il contient le nombre).

Essai:

> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7]);
true
> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7,12]);
false

MATL, 5 octets

t&+m~

Cela génère un tableau qui est véridique si toutes les entrées le sont 1et Falsey sinon. Voici une démo pour montrer diverses valeurs de vérité / falsey dans MATL .

Essayez-le en ligne

Explication

        % Implicitly grab input
t       % Duplicate
&+      % Compute sum of each element with every other element (2D Matrix)
m       % Check which members of the input are present in this matrix of sums
~       % Negate the result to yield a truthy value for sum-free sets
        % Implicitly display truthy/falsey value

Mathematica, 23 octets

{}==#⋂Tr/@#~Tuples~2&

Haskell, 32 , 30 octets

Solution simple:

f x=and[a+b/=c|a<-x,b<-x,c<-x]

Deux octets enregistrés par @Lynn

Julia, 18 octets

!x=x∩(x'.+x)==[]

Essayez-le en ligne!

J, 18 10 8 octets

8 octets économisés grâce aux miles, et 2 grâce à FrownyFrog!

-:]-.+/~

Correspond à la liste d'origine avec la différence définie des sommes tabulées. Cela équivaut à:

(-: (] -. +/~)) y

pour entrée y. Cela se traduit par:

y -: (] -. +/~) y
y -: (y -. +/~ y)

+/~renvoie une table de sommes en utilisant y. Car y =: 16 1 4 9cela donne:

   +/~ 16 1 4 9
32 17 20 25
17  2  5 10
20  5  8 13
25 10 13 18

Ensuite, nous utilisons -., qui produit une liste composée de tous les éléments yne figurant pas dans ce tableau. Si la liste est sans somme, cela produira la même liste. Ensuite, -:vérifie l'égalité des listes, ce qui produit la sortie souhaitée.

Ancien, 18 octets

[:-.[:>./^:_+/~e.]

+/~crée un tableau des valeurs de l'ensemble ajouté à lui-même et e.vérifie si ces membres se trouvent dans l'ensemble d'origine. Le reste de cela annule l'élément maximal.

Rétine , 45 44 octets

\d+
<$&$*1>
$
$`$`
M`(<1*)>.*<(1*>).*\1\2
^0

L'entrée est une liste décimale de nombres séparés par des virgules. La sortie est 0(fausse) ou 1(véridique).

Essayez-le en ligne! (La première ligne active une suite de tests séparée par saut de ligne.)

Explication

Étape 1: substitution

\d+
<$&$*1>

Cela convertit tous les éléments de l'entrée en unaire et les encapsule <...>. Le but des crochets angulaires est de distinguer une liste ne contenant que 0d'une liste vide (puisque la représentation unaire de 0est elle-même vide).

Étape 2: substitution

$
$`$`

Nous répétons la chaîne 3 fois en l'ajoutant deux fois à la fin.

Étape 3: Match

M`(<1*)>.*<(1*>).*\1\2

Nous essayons maintenant de trouver trois nombres dans le résultat de sorte que les deux premiers s'additionnent au troisième. Ces correspondances sont comptées (cela ne compte pas réellement tous ces tuples, car les correspondances ne peuvent pas se chevaucher, mais si un tel tuple existe, il sera trouvé). Par conséquent, nous obtenons 0des ensembles sans somme et quelque chose de positif autrement.

Étape 4: Match

^0

Depuis l'étape précédente a donné à l'opposé de ce que nous voulons, nous nions le résultat en comptant les matches de ce ^0qui est 1pour l' entrée 0et 0pour tout le reste.

Octave, 29 21 25 octets

@(s)~[ismember(s,s+s') 0]

Merci à Suever ! Il renvoie un tableau. J'ai ajouté 0à la fin pour faire []devenir sans somme. Pour vérifier véridique et falsey dans Octave, vous pouvez le faire:

> f=@(s)~[ismember(s,s+s') 0]

> if f([]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([0]) "sum-free" else "not sum-free" end
ans = not sum-free

> if f([4]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([1 3]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([2 4]) "sum-free" else "not sum-free" end
ans = not sum-free

Une alternative qui renvoie 0 ou 1 est:

@(s)~numel(intersect(s+s',s))

Clojure, 47 37 octets

#(=(for[a % b % :when(%(+ a b))]a)[])

solution assez simple. utilise la compréhension de liste pour trouver tous les éléments dont la somme est égale à un autre élément.

Variante de 38 octets:

#(every? nil?(for[a % b %](%(+ a b))))

Perl 6 ,  24 21 20  19 octets

{not any (@_ X+@_)X==@_}
{so all (@_ X+@_)X!==@_}
{not @_ (&)(@_ X+@_)}
{not @_∩(@_ X+@_)}

{!(@_∩(@_ X+@_))}

L'entrée est une valeur positionnelle comme une liste .
(un ensemble est un associatif , vous devrez donc faire appel .keysà lui.)

Tester:

#! /usr/bin/env perl6
use v6.c;
use Test;

my @sum-free = (
  (),
  (4,),
  (1, 5, 7),
  (16, 1, 4, 9),
);

my @not-sum-free = (
  (0,),
  (1, 4, 5, 7),
  (3, 0),
  (16, 1, 4, 8),
);

my @tests = ( |(@sum-free X=> True), |(@not-sum-free X=> False) );

plan +@tests;

# store the lambda in lexical namespace for clarity
my &sum-free-set = {!(@_∩(@_ X+@_))}

for @tests -> $_ ( :key(@list), :value($expected) ) {
  is sum-free-set(@list), $expected, .gist
}

1..8
ok 1 - () => True
ok 2 - (4) => True
ok 3 - (1 5 7) => True
ok 4 - (16 1 4 9) => True
ok 5 - (0) => False
ok 6 - (1 4 5 7) => False
ok 7 - (3 0) => False
ok 8 - (16 1 4 8) => False

Mathematica 63 62 42 octets

Cette version plus courte a bénéficié de la soumission de A Simmons. Aucun élément ne doit être supprimé de la liste avant d' IntegerPartitionsêtre appliqué.

Si un élément ne peut pas être partitionné en deux entiers (chacun de la liste), alors il en IntegerPartitions[#,{2},#]=={}est ainsi. Andvérifie si cela vaut pour chaque élément de la liste. Si c'est le cas, la liste est sans somme.

And@@(IntegerPartitions[#,{2},#]=={}&/@#)&

Exemples

 And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{2, 4, 9, 13}

Faux

 And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{1, 5, 7}

Vrai

Il y a un 2, mais pas de nombres impairs qui diffèrent par 2.

 And@@(IntegerPartitions[#,{2},#]=={}&/@#)&@{2, 3, 7, 11, 17, 23, 29, 37, 41, 47, 53, 59, 67, 71}

Vrai

Rubis, 36 octets

Construit un produit cartésien de l'ensemble par rapport à lui-même et trouve la somme de tous les éléments, puis vérifie l'intersection avec l'ensemble d'origine. L'entrée est des tableaux, mais dans Ruby, ils ont suffisamment d'opérations définies pour que cela fonctionne de toute façon.

-1 octet sur ma solution d'origine (utilisée à la &place de -et comparée à []) en raison de l'inspiration de @feersum

Essayez-le ici!

->s{s-s.product(s).map{|x,y|x+y}==s}

Python, 40 octets

lambda s:s^{a+b for a in s for b in s}>s

^ = différence symétrique, nouvel ensemble avec des éléments dans les deux ensembles mais pas les deux

> Vrai si l'ensemble gauche est un surensemble de l'ensemble droit.

Brachylog , 13 octets

'(p:?+L:?x'L)

Explication

'(          )  True if what's in the parentheses is impossible, false otherwise
  p            Get a permutation of Input
   :?+L        L is the list of element-wise sums of the permutation with Input
       :?x'L   There is at least one element of Input in L

R, 39 36 octets

w<-function(s)!any(outer(s,s,'+')%in%s)

Appelez comme w(s), où sest l'ensemble (en fait le vecteur) de valeurs. Voici la sortie de certains cas de test:

> w(numeric(0)) # The empty set
[1] TRUE
> w(0)
[1] FALSE
> w(1)
[1] TRUE
> w(c(1, 5, 7))
[1] TRUE
> w(c(2, 4, 9, 13))
[1] FALSE

Où c()est la fonction de concaténation qui prend un tas de valeurs et en fait un vecteur.

EDIT: en faire une fonction anonyme pour économiser 3 octets, grâce à @MickyT.

function(s)!any(outer(s,s,'+')%in%s)

Raquette, 58 octets

(λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l))

Explication:

(λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l))
(λ(l)                                                 ) # Define a lambda function that takes in one parameter
     (andmap(λ(m)                                  )l)  # If for all m in l
                 (andmap(λ(n)                   )l)     # If for all n in l
                             (not(memq(+ n m)l))        # n + m is not in l

05AB1E , 9 5 octets

4 octets enregistrés grâce à l' urne Magic Octopus

ãOå_P

Essayez-le en ligne!

Explication

ã       # cartesian product
 O      # sum
  å     # check each if it exists in input
   _    # logical negation
    P   # product

APL, 8 octets

⊢≡⊢~∘.+⍨

Explication:

⊢         argument
 ≡        equals
  ⊢       argument
   ~      without 
    ∘.+⍨  sums of its elements

Tester:

      ( ⊢≡⊢~∘.+⍨ ) ¨ (1 5 7)(2 4 9 13)
1 0

Haskell, 30 octets

f s=and[x+y/=z|x<-s,y<-s,z<-s]

Je pense qu'il existe une solution plus courte qui est plus intéressante, mais je ne l'ai pas trouvée.

Ce sont 33 et 34 octets:

f s=and$((/=)<$>s<*>)$(+)<$>s<*>s
f s|q<-((-)<$>s<*>)=all(/=0)$q$q$s

En fait , 7 octets

;;∙♂Σ∩Y

Essayez-le en ligne!

;;∙♂Σ∩Y              Stack: [1,5,7]
;         duplicate         [1,5,7] [1,5,7]
 ;        duplicate         [1,5,7] [1,5,7] [1,5,7]
  ∙       cartesian product [1,5,7] [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
   ♂Σ     sum each          [1,5,7] [2,6,8,6,10,12,8,12,14]
     ∩    intersect         []
      Y   negate            1

TSQL, 47 octets

CREATE table T(a int)
INSERT T values(1),(5),(7),(12)

SELECT min(iif(a.a+b.a<>T.a,1,0))FROM T a,T b,T

Remarque: Cela ne s'exécutera qu'une seule fois, puis la table doit être supprimée ou supprimée pour s'exécuter à nouveau. L'éditeur de violon ne permet pas la création de tables. Par conséquent, le violon inclus dans ma réponse utilise 2 octets supplémentaires pour compenser cela - la version violon ne nécessite pas de nettoyage.

Violon

Perl, 46 octets

Code de 45 octets + ligne de commande de 1 octet (-p)

$_="$_ $_ $_"!~/(\b\d++.*)((?1))(??{$1+$2})/

Utilise une seule correspondance d'expression régulière avec la prise en charge par Perl des «expressions de code» à l'intérieur de l'expression régulière pour permettre l'évaluation dans une correspondance.

Pour contourner l'exigence selon laquelle l'entrée n'est pas triée, nous répétons la chaîne d'entrée trois fois. Cela garantit que le résultat est après les deux opérandes et permet de faire correspondre à nouveau le même chiffre (par exemple dans le cas d'une entrée 2 4).

Exemple d'utilisation:

echo "3 5 6 8" | perl -p entry.pl

Facteur, 47 octets

[ dup dup 2array [ Σ ] product-map ∩ { } = ]

• ∩ { } =est équivalent à mais plus court que intersects?.
• Σest plus court que mais équivalent à sum.

Merci, math.unicode !

code de test:

USING: arrays kernel math.unicode sequences sequences.product ;
IN: sum-free

: sum-free? ( seq -- ? )
  dup dup 2array [ Σ ] product-map ∩ { } = ;

USING: tools.test sum-free ;
IN: sum-free.tests

{ t } [ { 5 7 9 } sum-free? ] unit-test
{ f } [ { 2 4 9 13 } sum-free? ] unit-test
{ t } [ { } sum-free? ] unit-test
{ f } [ { 0 } sum-free? ] unit-test
{ t } [ { 1 } sum-free? ] unit-test
{ f } [ { 0 1 } sum-free? ] unit-test

Je suis convaincu que les deux premiers sont corrects. La question de savoir ce que devrait être le reste n'est pas claire, donc je pense que ça va pour l'instant.

PHP, 73 octets

+8 pour transformer l'extrait de code en programme, -8 sur les variables obsolètes grâce à insertusernamehere

<?foreach($argv as$p)foreach($argv as$q)if(in_array($p+$q,$argv))die;echo 1;

imprime 1pour true, sortie vide pour false
utilisation:php <filename> <value1> <value2> ...

fonction qualifiée pour les tests ( 94 86): retourne 1ou rien

function f($a){foreach($a as$p)foreach($a as$q)if(in_array($p+$q,$a))return;return 1;}

tests

function out($a){if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
$samples = [
    [], 1,
    [0], false,
    [1], 1,
    [0,1], false,
    [2, 4, 9, 13], false,
    [1,5,7], 1
];
while($samples)
{
    $a=array_shift($samples);
    $e=array_shift($samples);
    test($a,$e,f($a));
}

Java, 67 octets

s->!s.stream().anyMatch(p->s.stream().anyMatch(q->s.contains(p+q)))

L'entrée est a Set<Integer>. Tests:

import java.util.Arrays;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class SumFree {
    public static void main(String[] args) {
        sumFree(s->!s.stream()
            .anyMatch(p->s.stream()
                .anyMatch(q->s.contains(p+q)))); // formatted to avoid wrapping
    }

    public static void sumFree(Function<Set<Integer>, Boolean> func) {
        test(func);
        test(func, 4);
        test(func, 1, 5, 7);
        test(func, 16, 1, 4, 9);
        test(func, 1, 4, 5, 7);
        test(func, 0);
        test(func, 3, 0);
        test(func, 16, 1, 4, 8);
    }

    public static void test(Function<Set<Integer>, Boolean> func, Integer... vals) {
        Set<Integer> set = Arrays.stream(vals).collect(Collectors.toSet());
        System.out.format("%b %s%n", func.apply(set), set);
    }
}

Sortie:

true []
true [4]
true [1, 5, 7]
true [16, 1, 4, 9]
false [0]
false [1, 4, 5, 7]
false [0, 3]
false [16, 1, 4, 8]

Clojure, 34 octets

#(not-any? %(for[i % j %](+ i j)))

J'ai écrit cela avant de remarquer la précédente solution Clojure. Quoi qu'il en soit, celui-ci est plus compact car il utilise l'ensemble d'entrée comme predfonction pour not-any?.

Prolog (SWI) , 66 56 49 octets

A/B:-member(A,B).
-L:- \+ (E/L,F/L,G is E+F,G/L).

Essayez-le en ligne!