Zestaw nie zawiera sum, jeśli żadne dwa (niekoniecznie odrębne) elementy po dodaniu są częścią samego zestawu.

Na przykład {1, 5, 7}jest bez sumy, ponieważ wszystkie elementy są nieparzyste, a dwie nieparzyste liczby po dodaniu są zawsze parzyste. Z drugiej strony, {2, 4, 9, 13}nie jest to suma wolna, jak albo 2 + 2 = 4czy 4 + 9 = 13dodać razem z elementem zestawu.

Napisz program lub funkcję, która pobiera zestaw jako dane wejściowe i wyprowadza wartość Prawda, jeśli zestaw nie zawiera sum, a Falsy w przeciwnym razie.

Przykłady:

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 bajtów

Dzięki @FryAmTheEggman za uratowanie mi 3 bajtów.

!@sM*

Pakiet testowy .

!             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 bajtów

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

s powinien być zestawem Python.

Ciekawostka: sum-freeto anagram mojego imienia.

Galaretka , 5 bajtów

ṗ3ḅ-P

Wypróbuj online!

Jak to działa

ṗ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 bajtów

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

Dzięki Cᴏɴᴏʀ O'Bʀɪᴇɴ za uratowanie mi mnóstwa bajtów w nawiasach / nawiasach klamrowych. Dziękuję także Neilowi ​​za zwrócenie uwagi, że funkcja zwraca przeciwną wartość logiczną niż powinna.

Próbowałem zmniejszyć liczbę bajtów, zmieniając definicję, n.someale to nie działa, ponieważ niestety jest to funkcja prototypowa. W Array.prototype.mapJS może być lepsze rozwiązanie, ale niektóre funkcje są naprawdę fajne.

Zastanawiam się teraz, czy istnieje krótszy sposób niż .includesużycie czegoś takiego jak .indexOf i dodanie 1 (co dałoby prawdziwą wartość, gdyby zawierała liczbę).

Testowanie:

> (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 bajtów

t&+m~

Daje to tablicę, która jest prawdziwa, jeśli wszystkie wpisy są, 1i nie działa inaczej. Oto demo pokazujące różne wartości true / falsey w MATL .

Wypróbuj online

Wyjaśnienie

        % 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 bajty

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

Haskell, 32 , 30 bajtów

Proste rozwiązanie:

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

Dwa bajty zapisane przez @Lynn

Julia, 18 bajtów

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

Wypróbuj online!

J, 18 10 8 bajtów

8 bajtów zaoszczędzonych dzięki milom, a 2 dzięki FrownyFrog!

-:]-.+/~

Dopasowuje oryginalną listę z ustawioną różnicą sum tabelarycznych. Jest to równoważne z:

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

na wejście y. Przekłada się to na:

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

+/~zwraca tabelę sum za pomocą y. Do y =: 16 1 4 9tego otrzymujemy:

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

Następnie używamy -., który tworzy listę składającą się ze wszystkich elementów, których ynie ma w tej tabeli. Jeśli lista nie zawiera sum, spowoduje to utworzenie tej samej listy. Następnie -:sprawdza równość list, co daje pożądany wynik.

Stary, 18 bajtów

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

+/~tworzy tabelę wartości zestawu dodanego do siebie i e.sprawdza, czy te elementy są w oryginalnym zestawie. Reszta neguje maksymalny element.

Siatkówka , 45 44 bajtów

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

Dane wejściowe to dziesiętna lista liczb oddzielonych przecinkami. Dane wyjściowe to 0(fałsz) lub 1(prawda).

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).

Wyjaśnienie

Etap 1: Zmiana

\d+
<$&$*1>

Konwertuje wszystkie elementy danych wejściowych na jednoargumentowe i otacza je <...>. Celem nawiasów kątowych jest rozróżnienie listy zawierającej tylko 0pustą listę (ponieważ sama reprezentacja jedności 0jest pusta).

Etap 2: Zmiana

$
$`$`

Powtarzamy ciąg 3 razy, dodając go dwa razy na końcu.

Etap 3: Mecz

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

Teraz staramy się znaleźć w wyniku trzy liczby, tak aby dwie pierwsze sumowały się do trzeciej. Te dopasowania są liczone (to tak naprawdę nie liczy wszystkich takich krotek, ponieważ dopasowania nie mogą się pokrywać, ale jeśli taka krotka istnieje, zostanie znaleziona). W związku z tym otrzymujemy 0zestawy bez sumy, a w przeciwnym razie coś pozytywnego.

Etap 4: Mecz

^0

Ponieważ poprzedni etap dawał odwrotność tego, czego chcemy, negujemy wynik, licząc dopasowania, ^0które są 1przeznaczone do wprowadzania 0i 0do wszystkiego innego.

Oktawa, 29 21 25 bajtów

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

Dzięki Suever ! Zwraca tablicę. Dodałem 0na końcu, aby []stać się bez sumy. Aby sprawdzić prawdę i falsey w Octave, możesz to zrobić:

> 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

Alternatywą, która zwraca 0 lub 1, jest:

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

Clojure, 47 37 bajtów

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

całkiem proste rozwiązanie. używa rozumienia listy, aby znaleźć wszystkie elementy, których suma jest równa innemu elementowi.

Wariant 38 bajtów:

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

Perl 6 ,  24 21 20  19 bajtów

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

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

Dane wejściowe to dowolna wartość pozycyjna, taka jak lista .
( zestaw jest asocjatorem, więc musisz go przywołać .keys).

Test:

#! /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 bajty

Ta krótsza wersja skorzystała z przesłania A Simmonsa. Przed IntegerPartitionszastosowaniem żaden element nie musi zostać usunięty z listy .

Jeśli element nie może być podzielony na dwie liczby całkowite (każdy z listy), wówczas pozostaje IntegerPartitions[#,{2},#]=={}. Andsprawdza, czy dotyczy to każdego elementu na liście. Jeśli tak, lista nie zawiera sum.

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

Przykłady

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

Fałszywe

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

Prawdziwe

Istnieją 2, ale nie ma liczb nieparzystych, które różnią się o 2.

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

Prawdziwe

Rubinowy, 36 bajtów

Konstruuje iloczyn kartezjański zbioru względem siebie i znajduje sumę wszystkich elementów, a następnie sprawdza, czy nie ma przecięcia z oryginalnym zestawem. Dane wejściowe są tablicami, ale w Rubim mają wystarczająco dużo ustawionych operacji, aby i tak dobrze działały.

-1 bajt nad moim oryginalnym rozwiązaniem (zastosowanym &zamiast -i porównanym z []) z powodu inspiracji z @feersum

Wypróbuj tutaj!

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

Python, 40 bajtów

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

^ = różnica symetryczna, nowy zestaw z elementami w obu zestawach, ale nie w obu

> Prawda, jeśli lewy zestaw jest nadzbiorem prawego zestawu.

Brachylog , 13 bajtów

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

Wyjaśnienie

'(          )  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 bajtów

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

Wywołaj jako w(s), gdzie sjest zestaw (faktycznie wektor) wartości. Oto wynik niektórych przypadków testowych:

> 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

Gdzie c()jest funkcja konkatenacji, która bierze wiązkę wartości i czyni ją wektorem.

EDYCJA: Dzięki temu @MickyT jest anonimową funkcją do zapisywania 3 bajtów.

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

Rakieta, 58 bajtów

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

Wyjaśnienie:

(λ(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 bajtów

Oszczędność 4 bajtów dzięki Magic Octopus Urn

ãOå_P

Wypróbuj online!

Wyjaśnienie

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

APL, 8 bajtów

⊢≡⊢~∘.+⍨

Wyjaśnienie:

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

Test:

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

Haskell, 30 bajtów

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

Myślę, że istnieje krótsze rozwiązanie, które jest bardziej interesujące, ale go nie znalazłem.

Są to 33 i 34 bajty:

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

Właściwie 7 bajtów

;;∙♂Σ∩Y

Wypróbuj online!

;;∙♂Σ∩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 bajtów

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

Uwaga: To uruchomi się tylko raz, a następnie tabela musi zostać usunięta lub upuszczona, aby uruchomić ponownie. Edytor skrzypiec nie pozwala na tworzenie tabel. Dlatego skrzypce zawarte w mojej odpowiedzi wykorzystują 2 dodatkowe bajty, aby to zrekompensować - wersja skrzypek nie wymaga czyszczenia.

Skrzypce

Perl, 46 bajtów

45-bajtowy kod + 1-bajtowy wiersz poleceń (-p)

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

Używa pojedynczego dopasowania wyrażenia regularnego z obsługą Perla dla „wyrażeń kodu” w wyrażeniu regularnym, aby umożliwić ocenę w dopasowaniu.

Aby obejść wymaganie, że dane wejściowe są nieposortowane, powtarzamy łańcuch wejściowy trzy razy. Gwarantuje to, że wynik występuje po dwóch operandach i pozwala na ponowne dopasowanie tej samej cyfry (np. W przypadku wprowadzania2 4 ).

Przykład użycia:

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

Współczynnik, 47 bajtów

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

• ∩ { } =jest równoważne, ale krótszy niż intersects?.
• Σjest krótszy niż, ale równoważny sum.

Dzięki, math.unicode !

kod testowy:

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

Jestem tylko pewien, że pierwsze dwa są poprawne. Pytanie, jaka powinna być reszta, nie jest jasne, więc myślę, że na razie jest w porządku.

PHP, 73 bajty

+8, aby zmienić fragment kodu w program, -8 w przypadku przestarzałych zmiennych dzięki wstawcesernameherehere

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

drukuje 1dla true, pusty wydruk do false
użycia:php <filename> <value1> <value2> ...

kwalifikowana funkcja do testowania ( 94 86): zwraca 1lub nic

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

testy

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 bajtów

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

Dane wejściowe to Set<Integer>. Testy:

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);
    }
}

Wydajność:

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 bajty

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

Napisałem to, zanim zauważyłem wcześniejsze rozwiązanie Clojure. W każdym razie ten jest bardziej kompaktowy, ponieważ wykorzystuje zestaw danych wejściowych jako predfunkcję not-any?.

Prolog (SWI) , 66 56 49 bajtów

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

Wypróbuj online!