Подкачка сумм

24

Учитывая непустой список целых положительных чисел , ваша задача - определить количество уникальных значений± x ± y ± z ± (Икс,Y,Z,...)±Икс±Y±Z±...

Например, рассмотрим список . Существует восемь возможных способов создания сумм:(1,2,2)

  • +1+2+2+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

Существует шесть уникальных сумм , поэтому ответ .6{5,-5,1,-1,3,-3}6

Тестовые случаи

[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

Эталонное решение (оптимизирует по скорости, а не по размеру).

Если вы не можете обработать последний случай, потому что вы используете метод грубой силы или что-то подобное, это нормально.

счет

Это , поэтому выигрывает самое короткое действительное решение (измеряется в байтах).

Esolanging Fruit
источник
Должны ли мы обрабатывать случай, когда входные данные являются пустым массивом?
Час Браун
@ChasBrown, вход не является пустым, в соответствии с постом.
JungHwan Мин
Хм, я не могу понять, как работает третий контрольный пример, не могли бы вы объяснить, пожалуйста?
Эрик Outgolfer
@EriktheOutgolfer Эффективно говорит, что если ваш массив состоит из всех идентичных чисел (например [2,2,2,2,...]), ответ должен быть длиной массива + 1. Это потому, что в этом случае положение знаков не имеет значения, и только номер каждого вопроса
reffu
@reffu Это скорее шутка, похоже, она была включена туда по ошибке.
Эрик Outgolfer

Ответы:

13

Wolfram Language (Mathematica) , 27 байтов

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

Попробуйте онлайн!

Нахождение количества уникальных сумм с перестановкой знаков эквивалентно нахождению количества уникальных сумм подмножеств.

Доказательством будет добавление суммы входных данных к каждой из сумм с заменой знака и деление на два. Тогда есть очевидная биекция.

объяснение

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

Выполните итерацию по входным данным с начальным значением {0}: возьмите объединение между <current value>и <current value> + input element(отображает в списки).

Tr[1^ ... ]

Гольф версия Lengthфункции.

Юнг Хван Мин
источник
8

Желе , 6 байт

ŒPS€QL

Попробуйте онлайн!

Задний план

Пусть L - входной список, а {P, N} - разбиение на алгебраические слагаемые с положительными и отрицательными знаками. Спецификация испытания требует вычисления s {P, N} = сумма (P) - сумма (N) .

Однако, поскольку сумма (P) + сумма (N) = сумма (L) и сумма (L) не зависит от разбиения, мы имеем s {P, N} = сумма (P) - сумма (N) = сумма ( P) - (сумма (L) - сумма (P)) = 2 сумма (P) - сумма (L) .

Таким образом, каждому уникальному значению суммы (P) соответствует одно уникальное значение s {P, N} .

Как это работает

Œ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.
Деннис
источник
7

MATL , 11 10 байт

nW:qBGY*un

Попробуйте онлайн! Это порт ответа от Octav / MATLAB Луиса Мендо . Я все еще пытаюсь выучить MATL, и я решил опубликовать его вместе с объяснением, поскольку MATL является языком месяца.

Объяснение:

Вот подробное описание для тех, кто не знаком с программированием на основе стека в целом и MATL в частности.

Входной вектор неявно размещается в стеке. Обратите внимание, что когда операция выполняется над элементом в стеке, этот элемент удаляется из стека.

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

И затем он неявно выводит последний элемент в стеке.

Стьюи Гриффин
источник
1
Хорошее объяснение!
Луис Мендо
6

Python 2 , 52 байта

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

Попробуйте онлайн!

Использует двоичное представление числа для хранения достижимых сумм подмножеств.

XNOR
источник
1
Не могли бы вы объяснить, как это работает? Вы придумали это сами или это какой-то известный результат?
sundar - Восстановить Монику
1
@sundar Это не так сложно. Этот ответ вычисляет уникальные суммы (не смена знака), как и многие другие ответы. Каждый бит в k соответствует сумме. k<<nдобавляет n к каждой сумме. Ориентируясь с kмагазинами, эти новые суммы kсохраняются при сохранении всех предыдущих, а дублированные симы не записываются
H.PWiz
Ах, следы прорывов ведут к идее биекции JungHwan Min , это было главное понимание, которое я пропустил. Здесь каждая сумма подмножества представлена ​​1 в этой позиции в цепочке битов (причем начальная 1 в LSB представляет сумму 0 для пустого подмножества). Все еще не то, что я бы назвал "не так сложно", но это может быть просто моя неопытность. :)
sundar - Восстановить Монику
5

Haskell, 46 байтов

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

Попробуйте онлайн!

Вместо суммирования подмножеств входного списка, мы делаем все комбинации либо сохранения числа, либо замены его 0, например,

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

Это на два байта короче subsequences.

Ними
источник
Хороший ответ! Я надеялся, что что-то вроде f x=sum[1|i<-[0..sum x],elem i$sum<$>mapM(:[0])x]будет короче, чем импорт, но, видимо, это не так.
Линн
Хорошо, даже короче, чем перевод Mathematica, хотя я думаю, что он красивее:import Data.List;length.foldr((<*>)union.map.(+))[0]
Джон Пурди
5

R, 83 75 байт

-8 байт благодаря JayCe и Джузеппе

Создает матрицу всех возможных комбинаций (1, -1) для размера входного вектора, умножает ее на исходный вектор, чтобы получить суммы. Тогда уникально и найди длину результата.

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


Предыдущая версия:

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

Разоблаченный с комментариями:

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
  }
Эндрю Хейнс
источник
Сохранить несколько байт с t: TIO
Jayce
и sum(v|1)на байт корочеlength(v)
Джузеппе
4

Октава / MATLAB, 45 41 40 байт

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

Ввод - это вектор-столбец (используется в ;качестве разделителя).

Ошибки кода для последнего контрольного примера из-за ограничений памяти.

Это использует идею из ответа JungHwan Min (подмножества вместо чередующихся знаков), чтобы сохранить несколько байтов.

Попробуйте онлайн!

Луис Мендо
источник
3

Python 3 , 61 байт

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

Попробуйте онлайн!

Рекурсивный подход, отслеживание уникальных сумм подмножеств.

Самое интересное, что это бьет itertoolsс большим отрывом:

76 байт

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

Попробуйте онлайн!

фонтанчик для питья
источник
3

Атташе , 29 байт

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

Попробуйте онлайн!

Это работает путем сворачивания ±оператора над списком ввода, затем взятия ±этого списка и подсчета уникальных атомов массива.

Вот несколько примеров того, как работает складывание:

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]

Затем мы генерируем все перестановки последнего знака, применяя PlusMinus еще раз.

Более эффективная версия, 31 байт

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

Попробуйте онлайн! Это не делает тайм-аут в финальном тестовом примере, поскольку не генерирует ненужных комбинаций.

Конор О'Брайен
источник
3

R , 62 байта

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

Попробуйте онлайн!

Алгоритм портов Денниса. Он наиболее близок к ответам Octave / MATL, поскольку использует аналогичный растровый и матричный продукт для включения / исключения терминов.

Giuseppe
источник
2

Утилиты Bash + GNU, 49 байт

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

Попробуйте онлайн!

Ввод в виде списка через запятую в командной строке.

объяснение

               ${@//,/{+,-\}}                      # 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
Цифровая травма
источник
2

машинный язык x86_64 для Linux, 31 29 байт

 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

Попробуйте онлайн!

Вдохновленный ответом @ xnor. Требуется машина с POPCNTинструкцией.

ceilingcat
источник
1

APL (Dyalog Classic) , 34 33 32 байта

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

Попробуйте онлайн!

Спасибо @ngn за -1 байт!

Zachary
источник
1-⍨≢⍵->≢1↓⍵
НГН
+.×⍨->+.×
нгн
Боюсь, последний не работает.
Захари
К сожалению, я не знаю, почему я думал, что вы применяете +. × к векторам ... извините
ngn
1

Чисто , 82 байта

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

Попробуйте онлайн!

Определяет функцию, ? :: [Int] -> Intиспользуемую f :: [Int] -> ([Int] -> Int)в качестве помощника для уменьшения каждой возможной суммы после сложения или вычитания.

Οurous
источник
Вот отличная версия эталонного решения в Haskell; не уверен, сколько это может перенести на Чистую, но вы могли бы получить что-то из этого.
Esolanging Fruit
@EsolangingFruit Спасибо, но он уже использует тот же подход, и я не могу найти способ сократить его даже при использовании эталонного решения.
Οurous
1

APL (Dyalog Classic) , 21 байт

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

Попробуйте онлайн!

объяснение

2(⍴⍨⊤∘⍳*)⍴

Последовательность функций, эквивалентная {((⍴⍵)⍴2)⊤⍳(⍴⍵)}, которая генерирует матрицу, которая имеет двоичные представления от 0 до длины ввода в виде столбцов

1-2×

Карты 1с на -1с и 0с на 1с

⊢+.×

Матричное умножение с вводом, которое дает массив всех возможных сумм

⍴∘∪

Удалить дубликаты, затем сосчитать

TwiNight
источник
1

Java 8, 207 83 44 байта

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

Порт @ xnor's Python 2 ответа .
-39 байтов благодаря @Jakob .

Попробуйте онлайн .

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`
Кевин Круйссен
источник
2
44 байта - это все, что нам нужно! Принимая поток Long: s->Long.bitCount(s.reduce(1l,(a,e)->a|a<<e)).
Якоб
@ Якоб Спасибо! Я всегда забываю .reduce( .bitCountа также могу добавить ..>.>) -39 байтов прямо здесь! :)
Кевин Круйссен
1
Также я только что сделал версию с произвольной точностью . Похоже, самый дешевый способ сделать это по-прежнему с помощью растрового изображения, а не наборов.
Якоб
1

Java 8, 85 байт

Еще один порт Java от ответа xnor . Как и в исходном ответе, здесь используется битовая карта произвольной точности, чтобы не было верхнего предела размера суммы подмножества.

Это лямбда от последовательного java.util.stream.Stream<Integer>до int.

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

Попробуйте онлайн

Обратите внимание, что объединитель (третий аргумент reduce) не используется, поскольку поток является последовательным. Функция, которую я выбрал, является произвольной.

Jakob
источник
1

Юлия 0,6 , 54 52 байта

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

Попробуйте онлайн!

( -2 байта путем замены ¬на ~, спасибо Джо Кингу )

Работает для всех тестовых случаев. Использует трансляцию для сбора всех возможных сумм, а затем подсчитывает их.

Объяснение:

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

Старое решение:

Юлия 0,6 , 64 байта

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

Попробуйте онлайн!

Работает для входных массивов длиной до 63 (поэтому не работает для последнего контрольного примера, что хорошо в соответствии с OP).

Объяснение:

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 - Восстановить Монику
источник
0

JavaScript (Babel Node) , 64 байта

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

Попробуйте онлайн!

Это не будет работать для последнего теста.


Более эффективное решение (работает на последнем тестовом примере):

JavaScript (Babel Node) , 71 байт

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

Попробуйте онлайн!


Это не будет работать в реальном браузере из-за Array#smoosh.

Благодаря Bubbler, [x+f,x-f]-> [x+f,x]сохраняет 2 байта.

ТТГ
источник
Вы можете использовать [x+f,x]вместо [x+f,x-f]( доказательство JungHwan Мин ).
Bubbler
+2 байта для версии ES6:F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size
Нейл
@Neil, и ... [...s,...s.map(x=>x+f)], s.concat(s.map(x=>x+f))и, s,s.map(x=>s.push(x+f))доля такой же длины ...
TSH