Bei einer nicht leeren Liste positiver Ganzzahlen $(x, y, z, \dots)$ müssen Sie die Anzahl der eindeutigen Werte von ± x ± y ± z ± … bestimmen.$\pm x \pm y \pm z \pm \dots$

Betrachten Sie beispielsweise die Liste $(1, 2, 2)$ . Es gibt acht Möglichkeiten, Summen zu erstellen:

• $+ 1 + 2 + 2 \to +5$
• $+ 1 + 2 − 2 \to +1$
• $+ 1 − 2 + 2 \to +1$
• $+ 1 − 2 − 2 \to −3$
• $− 1 + 2 + 2 \to +3$
• $− 1 + 2 − 2 \to −1$
• $− 1 − 2 + 2 \to −1$
• $− 1 − 2 − 2 \to −5$

Es gibt sechs eindeutige Summen , daher lautet die Antwort 6 .$\{5, -5, 1, -1, 3, -3\}$$6$

Testfälle

[1, 2] => 4
[1, 2, 2] => 6
[s]*n => n+1
[1, 2, 27] => 8
[1, 2, 3, 4, 5, 6, 7] => 29
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] => 45
[1, 7, 2, 8, 3, 1, 6, 8, 10, 9] => 56
[93, 28, 92, 100, 43, 66, 2, 98, 2, 52, 57, 75, 39, 77, 45, 15, 13, 82, 81, 20, 68, 14, 5, 3, 72, 56, 57, 1, 23, 25, 76, 59, 60, 71, 71, 24, 1, 3, 72, 84, 72, 28, 83, 62, 66, 45, 21, 28, 49, 57, 70, 3, 44, 47, 1, 54, 53, 56, 36, 20, 99, 9, 89, 74, 1, 14, 68, 47, 99, 61, 46, 26, 69, 21, 20, 82, 23, 39, 50, 58, 24, 22, 48, 32, 30, 11, 11, 48, 90, 44, 47, 90, 61, 86, 72, 20, 56, 6, 55, 59] => 4728

Referenzlösung (optimiert für Geschwindigkeit und nicht Größe).

Wenn Sie den letzten Fall nicht behandeln können, weil Sie eine Brute-Force-Methode oder ähnliches verwenden, ist das in Ordnung.

Wertung

Das ist Code-Golf , also gewinnt die kürzeste gültige Lösung (gemessen in Bytes).

Wolfram Language (Mathematica) , 27 Byte

Tr[1^Fold[#⋃+##&,{0},#]]&

Probieren Sie es online!

Das Ermitteln der Anzahl der Summen für den Austausch eindeutiger Vorzeichen entspricht dem Ermitteln der Anzahl der Summen für eindeutige Teilmengen.

Ein Beweis würde das Addieren der Summe der Eingabe zu jeder der Vorzeichentauschsummen und das Teilen durch zwei beinhalten. Dann gibt es eine offensichtliche Verzweigung.

Erläuterung

Fold[#⋃+##&,{0},#]

Durchlaufen Sie die Eingabe mit dem Anfangswert {0}: Nehmen Sie die Vereinigung zwischen <current value>und <current value> + input element(ordnet auf Listen zu).

Tr[1^ ... ]

Golf-Version der LengthFunktion.

Gelee , 6 Bytes

ŒPS€QL

Probieren Sie es online!

Hintergrund

Sei L die Eingabeliste und {P, N} eine Aufteilung in algebraische Summanden mit positiven und negativen Vorzeichen. Die Herausforderungsspezifikation erfordert die Berechnung von s _{{P, N}} = Summe (P) - Summe (N) .

Da jedoch Summe (P) + Summe (N) = Summe (L) und Summe (L) nicht von der Partition abhängen, haben wir s _{{P, N}} = Summe (P) - Summe (N) = Summe ( P) - (Summe (L) - Summe (P)) = 2Summe (P) - Summe (L) .

Somit entspricht jeder eindeutige Wert von sum (P) einem eindeutigen Wert von s _{{P, N}} .

Wie es funktioniert

ŒPS€QL  Main link. Argument: A (array)

ŒP      Powerset; generate all subarrays of A.
  S€    Take the sum of each.
    Q   Unique; deduplicate the sums.
     L  Take the length.

MATL , 11 10 Bytes

nW:qBGY*un

Probieren Sie es online! Dies ist eine Portierung von Luis Mendos Octave / MATLAB- Antwort. Ich versuche immer noch, MATL zu lernen, und ich dachte, ich würde es zusammen mit einer Erklärung posten, da MATL die Sprache des Monats ist.

Erläuterung:

Hier finden Sie eine Anleitung für alle, die mit Stack-basierter Programmierung im Allgemeinen und MATL im Besonderen nicht vertraut sind.

Der Eingabevektor wird implizit auf den Stapel gelegt. Beachten Sie, dass beim Ausführen einer Operation für ein Element im Stapel dieses Element aus dem Stapel entfernt wird.

                % Stack:
                % [1, 2, 2]
n               % Counts the number of elements of the vector on the top of the stack.
                % Stack:
                % [3]
 W              % Raise 2^x, where x is the number above it in the stack
                % Stack:
                % [8]
  :             % Range from 1...x, where x is the number above it in the stack.                    % Stack:
                % [1, 2, 3, 4, 5, 6, 7, 8]
   q            % Decrement. Stack:
                % [0, 1, 2, 3, 4, 5, 6, 7]
    B           % Convert to binary. Stack:
                % [0,0,0; 0,0,1; 0,1,0; 0,1,1; 1,0,0; 1,0,1; 1,1,0; 1,1,1] 
     G          % Push input again. Stack:           
                % [0,0,0; 0,0,1; 0,1,0; 0,1,1; 1,0,0; 1,0,1; 1,1,0; 1,1,1], [1; 2; 2]
      Y*        % Matrix multiplication of the two elements on the stack.
                % Stack:
                % [0; 2; 2; 4; 1; 3; 3; 5]
        u       % Keep only unique elements. Stack:
                % [0; 2; 4; 1; 3; 5]
         n      % Number of elements in the vector. Stack:
                % [6]

Und dann gibt es implizit das letzte Element auf dem Stapel aus.

Python 2 , 55 Bytes

s={0}
for n in input():s|={t+n for t in s}
print len(s)

Probieren Sie es online!

Python 2 , 52 Bytes

k=1
for n in input():k|=k<<n
print bin(k).count('1')

Probieren Sie es online!

Verwendet die binäre Darstellung einer Zahl zum Speichern der erreichbaren Teilmengen.

05AB1E , 4 Bytes

æOÙg

Verwendet den gleichen Ansatz wie in Dennis 'Jelly-Antwort .

Probieren Sie es online!

Haskell, 46 Bytes

import Data.List
length.nub.map sum.mapM(:[0])

Probieren Sie es online!

Anstatt die Teilmengen der Eingabeliste zu summieren, werden alle Kombinationen vorgenommen, indem entweder eine Zahl beibehalten oder diese ersetzt wird 0, z

mapM(:[0])[1,2,3] -> [[1,2,3],[1,2,0],[1,0,3],[1,0,0],[0,2,3],[0,2,0],[0,0,3],[0,0,0]]

Dies ist zwei Bytes kürzer als subsequences.

R 83 75 Bytes

-8 Bytes dank JayCe und Giuseppe

Erstellt eine Matrix aller möglichen Kombinationen von (1, -1) für die Größe des Eingabevektors und multipliziert diese mit dem ursprünglichen Vektor, um die Summen zu erhalten. Dann einmalig und finde die Länge des Ergebnisses.

function(v)nrow(unique(t(t(expand.grid(rep(list(c(1,-1)),sum(v|1)))))%*%v))

vorherige Version:

f=function(v)nrow(unique(as.matrix(expand.grid(rep(list(c(1,-1)),length(v))))%*%v))

Ungolfed mit Kommentaren:

f=function(vector){

  List=rep(list(c(1,-1)),length(vector))   ## Create a list with length(vector) elements, all (1,-1)

  Combinations=expand.grid(Length)    ## get all combinations of the elements of the list, e.g, 1,-1,1,1,-1,1

  Matrix=as.matrix(Combinations)   ## convert to matrix

  Results=Matrix%*%vector   ## multiply the matrix original vector to get a Nx1 matrix

  Unique_results=unique(Results)   ## unique the results

  nrow(Unique_results)   ## length = number of rows of unique values
  }

Octave / MATLAB, 45 41 40 Bytes

@(x)nnz(unique(dec2bin(0:2^nnz(x)-1)*x))

Die Eingabe ist ein Spaltenvektor (mit ; als Trennzeichen verwendet wird).

Die Codefehler für den letzten Testfall aufgrund von Speicherbeschränkungen.

Hierbei wird eine Idee aus der Antwort von JungHwan Min verwendet (Teilmengen statt Wechselzeichen ), um einige Bytes zu sparen.

Probieren Sie es online!

Pari / GP , 39 Bytes

a->#[1|n<-Vec(prod(i=1,#a,1+x^a[i])),n]

$\prod_{i \in a}(1+x^i)$$a$

Probieren Sie es online!

Python 3 , 61 Bytes

f=lambda a,s={0}:a and f(a[1:],s|{u+a[0]for u in s})or len(s)

Probieren Sie es online!

Rekursiver Ansatz, der die eindeutigen Summen von Teilmengen verfolgt.

Der wahre Spaß ist, dass dies itertoolsmit großem Abstand schlägt :

76 Bytes

lambda a:len({*map(sum,product(*([0,x]for x in a)))})
from itertools import*

Probieren Sie es online!

Pyth , 5 Bytes

l{sMy

Verwendet den gleichen Ansatz wie in Dennis 'Jelly-Antwort .

Probieren Sie es hier aus.

Attache , 29 Bytes

{#Unique[Flat!±_]}@Fold[`±]

Probieren Sie es online!

Dies funktioniert, indem der ±Operator über die Eingabeliste gefaltet und dann genommen wird± diese Liste dann genommen und die eindeutigen Atome des Arrays gezählt werden.

Hier einige Beispiele, wie das Falten funktioniert:

Fold[`±][ [1,2] ] == 1 ± 2
                  == [1 + 2, 1 - 2]
                  == [3, -1]
Fold[`±][ [1,2,2] ] == (1 ± 2) ± 2
                    == [3, -1] ± 2
                    == [[3 + 2, 3 - 2], [-1 + 2, -1 - 2]]
                    == [[5, 1], [1, -3]]
                    == [5, 1, 1, -3]
Fold[`±][ [4,4,4,4] ] == (4 ± 4) ± 4 ± 4
                      == [8, 0] ± 4 ± 4
                      == [[12, 4], [4, -4]] ± 4
                      == [[[16, 8], [8, 0]], [[8, 0], [0, -8]]]
                      == [16, 8, 8, 0, 8, 0, 0, -8]
                      == [16, 8, 0, -8]

Dann generieren wir alle Permutationen des Endzeichens, indem wir PlusMinus erneut anwenden.

Eine effizientere Version, 31 Bytes

`#@(q:=Unique@Flat@`±)@Fold[q]

Probieren Sie es online! Beim endgültigen Testfall tritt keine Zeitüberschreitung auf, da keine unnötigen Kombinationen generiert werden.

R , 62 Bytes

function(V)sum(unique(c(V%*%combn(rep(0:1,L),L<-sum(V|1))))|1)

Probieren Sie es online!

Portiert Dennis 'Algorithmus. Es kommt den Octave / MATL-Antworten am nächsten, da es ein ähnliches Bitmap- und Matrixprodukt zum Einschließen / Ausschließen von Begriffen verwendet.

APL (Dyalog Classic) , 12 bis 11 Bytes

-1 danke an H.PWiz

≢⊃(+∪⊢)/⎕,0

Probieren Sie es online!

Perl 5 -p , 39 Bytes

s/^| /{+,-}/g;$_=grep!$s{eval$_}++,glob

Probieren Sie es online!

JavaScript (ES6), 63 Byte

f=([c,...a],s=n=!(o={}))=>c?f(a,s-c)|f(a,s+c)&&n:o[s]=o[s]||++n

Probieren Sie es online!

Schale , 5 Bytes

LumΣṖ

Probieren Sie es online!

Port of Dennis 'Jelly Antwort.

Erläuterung

LumΣṖ                     [1,2,2]
    Ṗ  Powerset           [[],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]]
  mΣ   Sum each           [0,1,2,3,2,3,4,5]
 u     Remove duplicates  [0,1,2,3,4,5]
L      Length             6

Perl 6 , 33 Bytes

{+set ([X](^2 xx$_)XZ*$_,)>>.sum}

Probieren Sie es online!

Bash + GNU-Dienstprogramme, 49 Bytes

eval echo "{,-}${@//,/{+,-\}}\;"|bc|sort -u|wc -l

Probieren Sie es online!

Eingabe in Form einer durch Kommas getrennten Liste in der Befehlszeile.

Erläuterung

               ${@//,/{+,-\}}                      # Replace commas with {+,-}
          "{,-}${@//,/{+,-\}}\;"                   # Build a brace expansion with {+,-} before every number and ; at the end
eval echo "{,-}${@//,/{+,-\}}\;"                   # Expand to give every combination expression, separated by ;
                                |bc                # Arithmetically evaluate each line
                                   |sort -u        # Remove duplicates
                                            wc -l  # Count

x86_64 Maschinensprache für Linux, 31 bis 29 Byte

 0:   31 d2                   xor    %edx,%edx
 2:   6a 01                   pushq  $0x1
 4:   58                      pop    %rax
 5:   8b 0c 97                mov    (%rdi,%rdx,4),%ecx
 8:   48 89 c3                mov    %rax,%rbx
 b:   ff c2                   inc    %edx
 d:   48 d3 e3                shl    %cl,%rbx
10:   48 09 d8                or     %rbx,%rax
13:   39 d6                   cmp    %ese,%edx
15:   7c ee                   jle    5 <+0x5>
17:   f3 48 0f b8 c0          popcnt %rax,%rax
1c:   c3                      retq

Probieren Sie es online!

Inspiriert von @ xnors Antwort. Benötigt eine Maschine mit der POPCNTAnweisung.

C (GCC) , 74 69 Bytes

f(a,b)int*a;{long k=1;for(;b--;k|=k<<a[b]);a=__builtin_popcountl(k);}

Probieren Sie es online!

C-Port von @ xnors Antwort

APL (Dyalog Classic) , 34 33 32 Bytes

{≢∪⍵+.×⍨↑{,⍵∘.,U}⍣(≢1↓⍵)⊢U←¯1 1}

Probieren Sie es online!

Danke an @ngn für -1 Byte!

Sauber , 82 Bytes

import StdEnv
f[]=length
f[h:t]=f t o foldr(\e l=removeDup[e+h,e-h:l])[]
?l=f l[0]

Probieren Sie es online!

Definiert die Funktion, ? :: [Int] -> Intmit der f :: [Int] -> ([Int] -> Int)nach einer Addition oder Subtraktion über jede mögliche Summe gekürzt wird.

APL (Dyalog Classic) , 21 Byte

⍴∘∪⊢+.×1-2×2(⍴⍨⊤∘⍳*)⍴

Probieren Sie es online!

Erläuterung

2(⍴⍨⊤∘⍳*)⍴

Ein äquivalenter Funktionszug {((⍴⍵)⍴2)⊤⍳(⍴⍵)}, der eine Matrix generiert, die die binären Darstellungen von 0 bis zur Länge der Eingabe als Spalten enthält

1-2×

Ordnet 1s zu -1s und 0s zu 1s zu

⊢+.×

Matrixmultiplikation mit der Eingabe, die ein Array aller möglichen Summen ergibt

⍴∘∪

Duplikate entfernen und zählen

Java 8, 207 83 44 Bytes

s->Long.bitCount(s.reduce(1L,(r,c)->r|r<<c))

Port von @ xnors Python 2-Antwort .
-39 Bytes dank @Jakob .

Probieren Sie es online aus .

s->               // Method with Long-Stream parameter and long return-type
  Long.bitCount(  //  Return the amount of 1s in the binary representation of:
    s.reduce(1L,  //   Result-Long, starting at 1
     (r,c)->      //   Loop pair-wise (result,current):
      r|          //    Bitwise-OR the result `r` with:
        r<<c))    //    result `r` bitwise left-shifted by the current `c`

Java 8, 85 Bytes

Ein weiterer Java-Port von xnors Antwort . Wie bei der ursprünglichen Antwort wird eine Bitmap mit willkürlicher Genauigkeit verwendet, sodass die Größe einer Teilmenge nicht nach oben begrenzt ist.

Es ist ein Lambda von einer sequentiellen java.util.stream.Stream<Integer>zu int.

s->s.reduce(java.math.BigInteger.ONE,(a,e)->a.or(a.shiftLeft(e)),(u,v)->u).bitCount()

Probieren Sie es online

Beachten Sie, dass der Kombinierer (das dritte Argument für reduce) nicht verwendet wird, da der Stream sequentiell ist. Die von mir gewählte Funktion ist beliebig.

Julia 0,6 , 54 52 Bytes

V->(~W=W==[]?0:∪([n=W[] -n].+~W[2:end]))(V)|>endof

Probieren Sie es online!

( -2 Bytes durch Ersetzen ¬durch ~, danke an Jo King )

Funktioniert für alle Testfälle. Nutzt Broadcast, um alle möglichen Beträge zu sammeln und zählt sie dann.

Erläuterung:

function g_(V)
  function inner(W)  #named ~ in golf version to save bytes
    W == [] ? 0 :    #return 0 when input empty (base case)
    ∪(               #unique elements of
      [n=W[] -n]     #take the first element and its negation
      .+             #broadcast-add that to each element of
      inner([2:end]) #sign-swapping sums of the rest of the array
     )
  end                #returns the list of unique elements out of those sums
  return endof(inner(V)) #return the length of that list
end

Ältere Lösung:

Julia 0,6 , 64 Bytes

N->endof(∪([2(i&2^~-j>0)-1 for i=0:~-2^(l=endof(N)),j=1:l]*N))

Probieren Sie es online!

Funktioniert für Eingabearrays mit einer Länge von bis zu 63 (funktioniert also nicht für den letzten Testfall, was laut OP in Ordnung ist).

Erläuterung:

function f_(N)
  endof(                            #length of
        ∪(                          #unique elements of
          [
           (i & 2^(j-1) > 0)        #check j'th bit (from right) of i
           * 2 - 1                  #convert bit value from (0,1)=>(-1,1)
           for i = 0:2^endof(N)-1,  #where i is numbers 0 to 2^length(N)-1
           j = 1:endof(N)           #and j is 1 to length(N) (i.e. the bits in i)
          ]                         #so we have a matrix [-1 -1 -1;1 -1 -1;1 -1 1;...]
          *                         #matrix multiply that with the input array, 
          N                         #thus calculating different combinations of 
         ))                         #sign-swapping sums
end

JavaScript (Babel Node) , 64 Byte

F=([f,...r],s=[0])=>f?F(r,s.flatMap(x=>[x+f,x])):new Set(s).size

Probieren Sie es online!

Dies funktioniert nicht für den letzten Testfall.

Effektivere Lösung (arbeitet am letzten Testfall):

JavaScript (Babel Node) , 71 Byte

F=([f,...r],s=[0])=>f?F(r,[...new Set(s.flatMap(x=>[x+f,x]))]):s.length

Probieren Sie es online!

In einem echten Browser funktioniert dies aufgrund von nicht Array#smoosh.

Dank Bubbler [x+f,x-f]-> [x+f,x]spart 2 Bytes.

Rot , 73 Bytes

func[b][s:[0]foreach n b[foreach m s[s: union s reduce[m + n]]]length? s]

Port of Dennis 'Python 2 Antwort. Behandelt nicht den letzten Testfall.

Probieren Sie es online!