Sumy do zamiany znaków

24

Biorąc pod uwagę niepustą listę dodatnich liczb całkowitych , Twoim zadaniem jest określenie liczby unikalnych wartości± x ± y ± z ± (x,y,z,)±x±y±z±

Na przykład rozważ listę . Istnieje osiem możliwych sposobów tworzenia sum:(1,2,2)

  • +1+2+2+5
  • +1+22+1
  • +12+2+1
  • +1223
  • 1+2+2+3
  • 1+221
  • 12+21
  • 1225

Istnieje sześć unikalnych sum , więc odpowiedź to 6 .{5,5,1,1,3,3}6

Przypadki testowe

[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

Rozwiązanie referencyjne (optymalizuje szybkość, a nie rozmiar).

Jeśli nie możesz poradzić sobie z ostatnim przypadkiem, ponieważ używasz metody brutalnej siły lub podobnej, nie ma sprawy.

Punktacja

To jest , więc wygrywa najkrótsze prawidłowe rozwiązanie (mierzone w bajtach).

Esolanging Fruit
źródło
Czy musimy obsługiwać przypadek, w którym wejściem jest pusta tablica?
Chas Brown
@ChasBrown dane wejściowe nie są puste, zgodnie z postem.
JungHwan Min
Hm, nie rozumiem, jak działa trzeci przypadek testowy, proszę wyjaśnić?
Erik the Outgolfer,
@EriktheOutgolfer To skutecznie mówi, że jeśli twoja tablica ma wszystkie identyczne liczby (np. [2,2,2,2,...]) Odpowiedzią powinna być długość tablicy + 1. Jest tak, ponieważ w tym przypadku pozycja znaków jest nieistotna i tylko liczba każdej sprawy
refffu
@reffu To raczej żart, wygląda trochę tak, jakby został tam uwzględniony przez błąd.
Erik the Outgolfer,

Odpowiedzi:

13

Wolfram Language (Mathematica) , 27 bajtów

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

Wypróbuj online!

Znalezienie liczby unikalnych sum wymiany znaków jest równoważne znalezieniu liczby unikalnych sum podzbioru.

Dowód wymagałby dodania sumy danych wejściowych do każdej sumy zamiany znaków i podzielenia przez dwa. Potem jest oczywisty bijection.

Wyjaśnienie

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

Iteruj przez dane wejściowe, przy czym początkowa wartość to {0}: weź związek między <current value>i <current value> + input element(mapy na listy).

Tr[1^ ... ]

Golfowa wersja Lengthfunkcji.

JungHwan Min
źródło
8

Galaretka , 6 bajtów

ŒPS€QL

Wypróbuj online!

tło

Niech L będzie listą wejściową, a {P, N} podział na algebraiczne zbiory ze znakami dodatnimi i ujemnymi. Specyfikacja wyzwania wymaga obliczenia s {P, N} = suma (P) - suma (N) .

Ponieważ jednak suma (P) + suma (N) = suma (L) i suma (L) nie zależy od podziału, mamy s {P, N} = suma (P) - suma (N) = suma ( P) - (suma (L) - suma (P)) = 2 suma (P) - suma (L) .

Zatem każda unikalna wartość sumy (P) odpowiada jednej unikalnej wartości s {P, N} .

Jak to działa

Œ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.
Dennis
źródło
7

MATL , 11 10 bajtów

nW:qBGY*un

Wypróbuj online! To jest port odpowiedzi Luisa Mendo na Octave / MATLAB . Wciąż próbuję nauczyć się MATL i pomyślałem, że opublikuję go wraz z wyjaśnieniem, ponieważ MATL jest językiem miesiąca.

Wyjaśnienie:

Oto lektura dla każdego, kto nie jest zaznajomiony z programowaniem stosowym w ogóle, a zwłaszcza z MATL-em.

Wektor wejściowy jest domyślnie umieszczony na stosie. Zauważ, że kiedy operacja jest wykonywana na elemencie na stosie, wówczas ten element jest usuwany ze stosu.

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

A następnie domyślnie wyprowadza ostatni element na stosie.

Stewie Griffin
źródło
1
Ładne wyjaśnienie!
Luis Mendo,
6

Python 2 , 52 bajty

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

Wypróbuj online!

Wykorzystuje binarną reprezentację liczby do przechowywania osiągalnych sum podzbiorów.

xnor
źródło
1
Czy możesz wyjaśnić, jak to działa? Czy sam to wymyśliłeś, czy jest to jakiś znany wynik?
Sundar - Przywróć Monikę
1
@sundar To nie jest takie skomplikowane. Ta odpowiedź oblicza unikalne sumy (bez zamiany znaków), jak wiele innych odpowiedzi. Każdy bit wk odpowiada sumie. k<<ndodaje n do każdej sumy. Zamawianie ze ksklepami tych nowych kwot przy kjednoczesnym zachowaniu wszystkich poprzednich, a zduplikowani Simowie nie są rejestrowani
H.PWiz
Ach, szlak breacrumbów prowadzi z powrotem do pomysłu JungHwana Min , który był głównym wglądem, którego mi brakowało. Tutaj każda suma podzbioru jest reprezentowana przez 1 w tej pozycji w łańcuchu bitów (z początkowym 1 w LSB reprezentującym sumę 0 dla pustego podzbioru). Nadal nie jest to coś, co nazwałbym „niezbyt skomplikowanym”, ale to może być po prostu mój brak doświadczenia w mówieniu. :)
zegar słoneczny - Przywróć Monikę
5

Haskell, 46 bajtów

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

Wypróbuj online!

Zamiast sumowania podzbiorów listy danych wejściowych, wykonujemy wszystkie kombinacje zachowania liczby lub zastąpienia jej 0np

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]]

To dwa bajty krótsze niż subsequences.

nimi
źródło
Niezła odpowiedź! Miałem nadzieję, że coś takiego f x=sum[1|i<-[0..sum x],elem i$sum<$>mapM(:[0])x]będzie krótsze niż import, ale najwyraźniej tak nie jest.
Lynn
Fajne, nawet krótsze niż tłumaczenie Mathematica, choć myślę, że jest ładniejsze:import Data.List;length.foldr((<*>)union.map.(+))[0]
Jon Purdy
5

R, 83 75 bajtów

-8 bajtów dzięki JayCe i Giuseppe

Tworzy macierz wszystkich możliwych kombinacji (1, -1) dla rozmiaru wektora wejściowego, mnoży to przez oryginalny wektor, aby uzyskać sumy. Następnie unikatowy i znajdź długość wyniku.

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


Poprzednia wersja:

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

Niegolfowany z komentarzami:

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
  }
Andrew Haynes
źródło
Zaoszczędź kilka bajtów za pomocą t: TIO
JayCe
i sum(v|1)jest bajt krótszy niżlength(v)
Giuseppe
4

Octave / MATLAB, 45 41 40 bajtów

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

Dane wejściowe to wektor kolumny (używany ;jako separator).

Błędy kodu dla ostatniego przypadku testowego z powodu ograniczeń pamięci.

Wykorzystuje pomysł z odpowiedzi JungHwan Min (podzbiory zamiast znaków naprzemiennych), aby zaoszczędzić kilka bajtów.

Wypróbuj online!

Luis Mendo
źródło
4

Pari / GP , 39 bajtów

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

ia(1+xi)a

Wypróbuj online!

alephalpha
źródło
To świetny sposób, aby to zrobić!
JungHwan Min
3

Python 3 , 61 bajtów

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

Wypróbuj online!

Podejście rekurencyjne, śledzenie unikalnych sum podzbiorów.

Prawdziwa zabawa polega na tym, że bije itertoolsto z dużym marginesem:

76 bajtów

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

Wypróbuj online!

Bubbler
źródło
3

Attache , 29 bajtów

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

Wypróbuj online!

Działa to poprzez złożenie ±operatora nad listą wejściową, następnie pobranie ±tej listy, a następnie zliczenie unikalnych atomów tablicy.

Oto kilka przykładów działania składania:

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]

Następnie generujemy wszystkie permutacje znaku końcowego, stosując ponownie PlusMinus.

Bardziej wydajna wersja, 31 bajtów

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

Wypróbuj online! To nie kończy się na końcowym przypadku testowym, ponieważ nie generuje niepotrzebnych kombinacji.

Conor O'Brien
źródło
3

R , 62 bajty

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

Wypróbuj online!

Algorytm Porty Dennisa. Jest najbliżej odpowiedzi Octave / MATL, ponieważ używa podobnego produktu bitmapowego i macierzowego do włączania / wyłączania terminów.

Giuseppe
źródło
2

JavaScript (ES6), 63 bajty

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

Wypróbuj online!

Arnauld
źródło
2

Łuska , 5 bajtów

LumΣṖ

Wypróbuj online!

Portowa odpowiedź Dennisa na galaretkę.

Wyjaśnienie

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
Fyr
źródło
Odpowiednik odpowiedzi w Pythonie , w zasadzie znak dla znaku.
isaacg
2

Narzędzia Bash + GNU, 49 bajtów

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

Wypróbuj online!

Dane wejściowe podane jako lista oddzielona przecinkami w wierszu polecenia.

Wyjaśnienie

               ${@//,/{+,-\}}                      # 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
Cyfrowa trauma
źródło
2

język maszynowy x86_64 dla systemu Linux, 31 29 bajtów

 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

Wypróbuj online!

Zainspirowany odpowiedzią @ xnor. Wymaga maszyny z POPCNTinstrukcją.

sufitowy
źródło
2

C (gcc) , 74 69 bajtów

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

Wypróbuj online!

Port C odpowiedzi @ xnor

sufitowy
źródło
1

APL (Dyalog Classic) , 34 33 32 bajty

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

Wypróbuj online!

Dzięki @ngn za -1 bajt!

Zacharý
źródło
1-⍨≢⍵->≢1↓⍵
ngn
+.×⍨->+.×
ngn
Ten drugi nie działa, obawiam się.
Zacharý
Ups, nie wiem, dlaczego myślałem, że nakładasz +. × na wektory ... przepraszam
ngn
1

Czysty , 82 bajty

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

Wypróbuj online!

Definiuje funkcję ? :: [Int] -> Intużywając f :: [Int] -> ([Int] -> Int)jako pomocnik w celu zmniejszenia nad każdą możliwą sumę po dodawanie lub odejmowanie.

Obrzydliwe
źródło
Oto golfowa wersja rozwiązania referencyjnego w Haskell; nie jestem pewien, ile to może przenieść do Clean, ale możesz być w stanie coś z tego wyciągnąć.
Esolanging Fruit
@EsolangingFruit Dzięki, ale już używa tego samego podejścia i nie mogę znaleźć sposobu, aby go skrócić nawet przy zastosowaniu rozwiązania referencyjnego.
tragiczny
1

APL (Dyalog Classic) , 21 bajtów

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

Wypróbuj online!

Wyjaśnienie

2(⍴⍨⊤∘⍳*)⍴

Ciąg funkcji równoważny {((⍴⍵)⍴2)⊤⍳(⍴⍵)}, który generuje macierz, która ma reprezentacje binarne od 0 do długości danych wejściowych jako kolumn

1-2×

Mapy 1s do -1s i 0s do 1s

⊢+.×

Mnożenie macierzy przez dane wejściowe, co daje tablicę wszystkich możliwych sum

⍴∘∪

Usuń duplikaty, a następnie policz

TwiNight
źródło
1

Java 8, 207 83 44 bajty

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

Port odpowiedzi @ xnor na Python 2 .
-39 bajtów dzięki @Jakob .

Wypróbuj online .

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`
Kevin Cruijssen
źródło
2
44 bajty to wszystko, czego potrzebujemy! Biorąc strumienia Long: s->Long.bitCount(s.reduce(1l,(a,e)->a|a<<e)).
Jakob
@Jakob Thanks! Zawsze zapominam o .reduce(i .bitCountrównie dobrze mogę dodać ..>.>) -39 bajtów tutaj! :)
Kevin Cruijssen
1
Właśnie stworzyłem wersję o dowolnej precyzji . Wygląda na to, że najtańszym sposobem na to jest bitmapa zamiast zestawów.
Jakob
1

Java 8, 85 bajtów

Inny port Java XNOR „s odpowiedź . Podobnie jak oryginalna odpowiedź, wykorzystuje bitmapę o dowolnej precyzji, dzięki czemu nie ma górnej granicy wielkości sumy podzbioru.

To lambda od sekwencyjnego java.util.stream.Stream<Integer>do int.

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

Wypróbuj online

Zauważ, że sumator (trzeci argument reduce) nie jest używany, ponieważ strumień jest sekwencyjny. Wybrana funkcja jest dowolna.

Jakob
źródło
1

Julia 0.6 , 54 52 bajty

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

Wypróbuj online!

( -2 bajtów zastępując ¬przy ~dzięki Jo Króla )

Działa dla wszystkich przypadków testowych. Wykorzystuje transmisję do zebrania wszystkich możliwych kwot, a następnie je zlicza.

Wyjaśnienie:

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

Starsze rozwiązanie:

Julia 0.6 , 64 bajty

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

Wypróbuj online!

Działa dla tablic wejściowych o długości do 63 (więc nie działa dla ostatniego przypadku testowego, co jest zgodne z OP).

Wyjaśnienie:

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
sundar - Przywróć Monikę
źródło
0

JavaScript (węzeł Babel) , 64 bajty

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

Wypróbuj online!

To nie zadziała w przypadku ostatniego testu.


Bardziej skuteczne rozwiązanie (działa na ostatniej walizce testowej):

JavaScript (węzeł Babel) , 71 bajtów

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

Wypróbuj online!


To nie zadziała w prawdziwej przeglądarce z powodu Array#smoosh.

Dzięki Bubblerowi [x+f,x-f]-> [x+f,x]oszczędza 2 bajty.

tsh
źródło
Możesz użyć [x+f,x]zamiast [x+f,x-f]( dowód JungHwan Min ).
Bubbler,
+2 bajty dla wersji ES6:F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size
Neil
@Neil i ... [...s,...s.map(x=>x+f)], s.concat(s.map(x=>x+f))i, s,s.map(x=>s.push(x+f))dzielą tę samą długość ...
tsh
0

Czerwony , 73 bajty

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

Odpowiedź Portu Dennisa na Python 2. Nie obsługuje ostatniego przypadku testowego.

Wypróbuj online!

Galen Iwanow
źródło