Sumas de intercambio de signos

24

Dada una lista no vacía de enteros positivos , su trabajo es determinar el número de valores únicos de± x ± y ± z ± ...(X,y,z,...)±X±y±z±...

Por ejemplo, considere la lista . Hay ocho formas posibles de crear sumas:(1,2,2)

  • +1+2+2+5 5
  • +1+2-2+1
  • +1-2+2+1
  • +1-2-2-3
  • -1+2+2+3
  • -1+2-2-1
  • -1-2+2-1
  • -1-2-2-5 5

Hay seis sumas únicas , por lo que la respuesta es .6{5,5,1,1,3,3}6 6

Casos de prueba

[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

Solución de referencia (optimiza la velocidad y no el tamaño).

Si no puede manejar el último caso porque usa un método de fuerza bruta o similar, está bien.

Tanteo

Este es el , por lo que gana la solución válida más corta (medida en bytes).

Fruta Esolanging
fuente
¿Tenemos que manejar el caso donde la entrada es la matriz vacía?
Chas Brown
@ChasBrown la entrada no está vacía, según la publicación.
JungHwan Min
Hm, no puedo entender cómo funciona el tercer caso de prueba, ¿podría explicarlo, por favor?
Erik the Outgolfer
@EriktheOutgolfer De hecho está diciendo que si su matriz es todos números idénticos (por ejemplo [2,2,2,2,...]) la respuesta debería ser la longitud de la matriz + 1. Esto se debe a que en este caso la posición de los signos es irrelevante y solo el número de cada asunto
refutar
@reffu Es más una broma, parece que se ha incluido allí por error.
Erik the Outgolfer

Respuestas:

13

Wolfram Language (Mathematica) , 27 bytes

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

Pruébalo en línea!

Encontrar el número de sumas únicas de intercambio de signos es equivalente a encontrar el número de sumas de subconjuntos únicos.

Una prueba implicaría agregar la suma de la entrada a cada una de las sumas de intercambio de signos y dividir por dos. Entonces, hay una biyección obvia.

Explicación

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

Itere a través de la entrada, siendo el valor inicial {0}: tome la unión entre <current value>y <current value> + input element(asigna en listas).

Tr[1^ ... ]

Versión de golf de la Lengthfunción.

JungHwan Min
fuente
8

Jalea , 6 bytes

ŒPS€QL

Pruébalo en línea!

Fondo

Sea L la lista de entrada y {P, N} una partición en sumandos algebraicos con signos positivos y negativos. La especificación de desafío requiere calcular s {P, N} = sum (P) - sum (N) .

Sin embargo, dado que sum (P) + sum (N) = sum (L) y sum (L) no dependen de la partición, tenemos s {P, N} = sum (P) - sum (N) = sum ( P) - (suma (L) - suma (P)) = 2sum (P) - suma (L) .

Por lo tanto, cada valor único de suma (P) corresponde a un valor único de s {P, N} .

Cómo funciona

Œ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
fuente
7

MATL , 11 10 bytes

nW:qBGY*un

Pruébalo en línea! Este es un puerto de la respuesta Octave / MATLAB de Luis Mendo . Todavía estoy tratando de aprender MATL, y pensé que lo publicaría, junto con una explicación, ya que MATL es el idioma del mes.

Explicación:

Aquí hay una lectura para cualquiera que no esté familiarizado con la programación basada en pila en general, y MATL en particular.

El vector de entrada se coloca implícitamente en la pila. Tenga en cuenta que cuando se realiza una operación en un elemento de la pila, ese elemento se elimina de la pila.

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

Y luego genera el elemento final en la pila implícitamente.

Stewie Griffin
fuente
1
Buena explicación!
Luis Mendo
6

Python 2 , 52 bytes

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

Pruébalo en línea!

Utiliza la representación binaria de un número para almacenar las sumas de subconjuntos alcanzables.

xnor
fuente
1
¿Podría explicar cómo funciona esto? ¿Se te ocurrió a ti mismo, o es algún resultado conocido?
sundar - Restablecer Monica
1
@sundar No es tan complicado. Esta respuesta calcula las sumas únicas (no el intercambio de signos) como muchas otras respuestas. Cada bit en k corresponde a una suma. k<<nagrega n a cada suma. Orándose con las ktiendas estas nuevas sumas kmientras se mantienen todas las anteriores, y los Sims duplicados no se registran
H.PWiz
Ah, el rastro de migas de pan lleva de regreso a la idea de biyección de JungHwan Min , esa fue la idea principal que me faltaba. Aquí cada suma de subconjuntos está representada por un 1 en esa posición en la cadena de bits (con el 1 inicial en el LSB que representa la suma 0 para el subconjunto vacío). Todavía no es algo que yo llamaría "no tan complicado", pero esa puede ser mi inexperiencia hablando. :)
sundar - Restablecer Monica
5

Haskell, 46 bytes

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

Pruébalo en línea!

En lugar de sumar los subconjuntos de la lista de entrada, hacemos todas las combinaciones de mantener un número o reemplazarlo 0, p. Ej.

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

Esto es dos bytes más corto que subsequences.

nimi
fuente
¡Buena respuesta! Esperaba que algo así f x=sum[1|i<-[0..sum x],elem i$sum<$>mapM(:[0])x]fuera más corto que la importación, pero aparentemente, no lo es.
Lynn
Agradable, incluso más corto que la traducción de Mathematica, aunque creo que es más bonito:import Data.List;length.foldr((<*>)union.map.(+))[0]
Jon Purdy
5

R, 83 75 bytes

-8 bytes gracias a JayCe y Giuseppe

Crea una matriz de todas las combinaciones posibles de (1, -1) para el tamaño del vector de entrada, multiplica esto por el vector original para obtener las sumas. Luego único y encuentra la longitud del resultado.

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


versión previa:

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

Ungolfed con comentarios:

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
fuente
Guarde algunos bytes con t: TIO
JayCe
y sum(v|1)es un byte más corto quelength(v)
Giuseppe
4

Octava / MATLAB, 45 41 40 bytes

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

La entrada es un vector de columna (que se usa ;como separador).

Los errores de código para el último caso de prueba debido a restricciones de memoria.

Esto utiliza una idea de la respuesta de JungHwan Min (subconjuntos en lugar de signos alternativos) para guardar algunos bytes.

Pruébalo en línea!

Luis Mendo
fuente
4

Pari / GP , 39 bytes

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

youna(1+Xyo)una

Pruébalo en línea!

alephalpha
fuente
¡Esa es una forma genial de hacerlo!
JungHwan Min
3

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)

Pruébalo en línea!

Enfoque recursivo, seguimiento de sumas de subconjuntos únicos.

La verdadera diversión es que esto supera itertoolspor un gran margen:

76 bytes

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

Pruébalo en línea!

Bubbler
fuente
3

Adjunto , 29 bytes

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

Pruébalo en línea!

Esto funciona doblando el ±operador sobre la lista de entrada, luego tomando ±esa lista y contando los átomos únicos de la matriz.

Aquí hay algunos ejemplos de cómo funciona el plegado:

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]

Luego generamos todas las permutaciones del signo final aplicando PlusMinus una vez más.

Una versión más eficiente, 31 bytes.

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

Pruébalo en línea! Esto no agota el tiempo en el caso de prueba final, ya que no genera combinaciones innecesarias.

Conor O'Brien
fuente
3

R , 62 bytes

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

Pruébalo en línea!

Puertos Dennis 'algoritmo. Es más cercano a las respuestas de Octave / MATL, ya que utiliza un mapa de bits similar y un producto de matriz para la inclusión / exclusión de términos.

Giuseppe
fuente
2

JavaScript (ES6), 63 bytes

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

Pruébalo en línea!

Arnauld
fuente
2

Bash + utilidades GNU, 49 bytes

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

Pruébalo en línea!

Entrada dada como una lista separada por comas en la línea de comandos.

Explicación

               ${@//,/{+,-\}}                      # 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
Trauma digital
fuente
2

lenguaje de máquina x86_64 para Linux, 31 29 bytes

 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

Pruébalo en línea!

Inspirado por la respuesta de @ xnor. Requiere una máquina con las POPCNTinstrucciones.

techo
fuente
1

APL (Dyalog Classic) , 34 33 32 bytes

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

Pruébalo en línea!

¡Gracias a @ngn por -1 byte!

Zacharý
fuente
1-⍨≢⍵->≢1↓⍵
ngn
+.×⍨->+.×
ngn
El último no funciona, me temo.
Zacharý
oops, no sé por qué pensé que estás aplicando +. × en los vectores ... lo siento
ngn
1

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

Pruébalo en línea!

Define la función ? :: [Int] -> Intusando f :: [Int] -> ([Int] -> Int)como ayuda para reducir cada suma posible después de una suma o resta.

Οurous
fuente
Aquí hay una versión de golf de la solución de referencia en Haskell; no estoy seguro de cuánto puede llevar a Clean, pero es posible que pueda sacar algo de él.
Esolanging Fruit
@EsolangingFruit Gracias, pero ya está utilizando el mismo enfoque y no puedo encontrar una manera de acortarlo incluso con la solución de referencia desarrollada.
Precioso
1

APL (Dyalog Classic) , 21 bytes

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

Pruébalo en línea!

Explicación

2(⍴⍨⊤∘⍳*)⍴

Un tren de funciones equivalente a {((⍴⍵)⍴2)⊤⍳(⍴⍵)}, que genera una matriz que tiene las representaciones binarias de 0 a la longitud de la entrada como columnas

1-2×

Mapas 1s a -1sy 0s a 1s

⊢+.×

Multiplicación matricial con la entrada, que proporciona una matriz de todas las sumas posibles

⍴∘∪

Eliminar duplicados, luego contar

TwiNight
fuente
1

Java 8, 207 83 44 bytes

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

Puerto de la respuesta de @ xnor's Python 2 .
-39 bytes gracias a @Jakob .

Pruébalo en línea .

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
fuente
2
¡44 bytes es todo lo que necesitamos! Tomando una corriente de Long: s->Long.bitCount(s.reduce(1l,(a,e)->a|a<<e)).
Jakob
@Jakob ¡Gracias! Siempre me olvido de .reduce(y .bitCounttambién podría agregar ..>.>) -39 bytes allí mismo. :)
Kevin Cruijssen
1
También acabo de hacer una versión de precisión arbitraria . Parece que la forma más barata de hacerlo todavía es con un mapa de bits en lugar de conjuntos.
Jakob
1

Java 8, 85 bytes

Otro puerto de Java de XNOR respuesta 's . Al igual que la respuesta original, utiliza un mapa de bits de precisión arbitraria para que no haya un límite superior en el tamaño de una suma de subconjuntos.

Es una lambda de secuencial java.util.stream.Stream<Integer>a int.

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

Pruébalo en línea

Tenga en cuenta que el combinador (el tercer argumento para reduce) no se utiliza, ya que la secuencia es secuencial. La función que elegí es arbitraria.

Jakob
fuente
1

Julia 0.6 , 54 52 bytes

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

Pruébalo en línea!

( -2 bytes reemplazando ¬con ~, gracias a Jo King )

Funciona para todos los casos de prueba. Utiliza la transmisión para recolectar todas las sumas posibles, luego las cuenta.

Explicación:

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

Solución anterior:

Julia 0.6 , 64 bytes

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

Pruébalo en línea!

Funciona para matrices de entrada con una longitud de hasta 63 (por lo que no funciona para el último caso de prueba, que está bien según OP).

Explicación:

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 - Restablece a Monica
fuente
0

JavaScript (nodo de Babel) , 64 bytes

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

Pruébalo en línea!

Esto no funcionará para el último caso de prueba.


Solución más efectiva (funciona en el último caso de prueba):

JavaScript (nodo de Babel) , 71 bytes

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

Pruébalo en línea!


Esto no funcionará en un navegador real debido a Array#smoosh.

Gracias a Bubbler, [x+f,x-f]-> [x+f,x]ahorra 2 bytes.

tsh
fuente
Puede usar [x+f,x]en lugar de [x+f,x-f]( prueba de JungHwan Min ).
Bubbler
+2 bytes para la versión ES6:F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size
Neil
@Neil, y ... [...s,...s.map(x=>x+f)], s.concat(s.map(x=>x+f))y s,s.map(x=>s.push(x+f))comparten la misma duración ...
tsh
0

Rojo , 73 bytes

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

Puerto de Dennis 'Python 2 respuesta. No maneja el último caso de prueba.

Pruébalo en línea!

Galen Ivanov
fuente