Повторные частичные суммы

23

Частичные суммы списка целых чисел [a 1 , a 2 , a 3 , ..., a n ] имеют вид

s 1 = a 1
s 2 = a 1 + a 2
s 3 = a 1 + a 2 + a 3
...
s n = a 1 + a 2 + ... + a n

Затем мы можем взять список частичных сумм [s 1 , s 2 , s 3 , ..., s n ] и снова вычислить его частичные суммы, чтобы создать новый список, и так далее.

Связанный: Итерированные форвардные различия

Входные данные:

  • Непустой список целых чисел
  • Положительное количество итераций,

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

Побеждает несколько байтов. Встроенные модули в порядке, даже если они полностью решают проблему.

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

f([-3, 4, 7, -1, 15], 1) == [-3, 1, 8, 7, 22]
f([-3, 4, 7, -1, 15], 3) == [-3, -5, 1, 14, 49]

Leaderboard:

Показать фрагмент кода

code-golf number arithmetic sequence array-manipulation XNOR
источник
Должны ли аргументы быть в том же порядке, или число итераций должно предшествовать списку чисел?
kirbyfan64sos
@ kirbyfan64sos Любой заказ.
xnor

Ответы:

14

J, 5 байт

+/\^:

Попробуйте его в Интернете на J.js .

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

  • /\ это наречие (функция, которая принимает левый аргумент), которое кумулятивно уменьшается на свой аргумент.

  • Таким образом , +/\это накопленная сумма глагол.

  • ^:является силовым соединением ; (f ^: n) yприменяется fв общей сложности nразy .

  • Поезд-соединение глагола +/\^:образует наречие, которое повторяет+/\ столько раз, сколько указано в его (левом) аргументе.

    x (+/\^:) yанализируется как (x (+/\^:)) y, что эквивалентно выполнению (+/\^:x) y.

Спасибо @Zgarb за помощь в объяснении.

Деннис
источник
13

Mathematica, 19 байт

Хорошо, если встроенные модули в порядке ...

Accumulate~Nest~##&

Определяет функцию с той же сигнатурой, что и в примерах задачи. Я уверен, благодаря длинному имениAccumulate что это будет легко побеждено языками гольфа и семьей APL, все же. :)

Чтобы развить комментарий LegionMammal978 для тех, кто не Mathematica:

##представляет последовательность параметров функции (которая похожа на список, который автоматически «всплывает», где бы он ни был вставлен, если вы более знакомы с этим термином из выбранного вами языка). ~Являются синтаксическим сахаром для функции инфикса вызова, так что если мы вызываем функцию с параметрами listи nи расширить все, мы получим:

Accumulate~Nest~##
Nest[Accumulate, ##]
Nest[Accumulate, list, n]

Что именно соответствует порядку аргументов, ожидаемому Nest.

Мартин Эндер
источник
Это интересно, используя инфиксную нотацию для 3 аргументов, используя SlotSequence...
LegionMammal978
9

Haskell, 26 23 байта

(!!).iterate(scanl1(+))

Это определяет анонимную функцию, вызываемую следующим образом:

> let f = (!!).iterate(scanl1(+)) in f [-3,4,7,-1,15] 3
[-3,-5,1,14,49]

Спасибо @nimi за сохранение 3 байта.

объяснение

(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument
Zgarb
источник
Очень хорошо! И спасибо за объяснение!
Джейк,
2
Go pointfree, то вы можете даже не указывать имя для функции: (!!).iterate(scanl1(+)).
Ними
@nimi Спасибо! Каким-то образом я решил, что композиция не будет работать в моих интересах здесь ...
Zgarb
9

APL, 9 8 байт

{+\⍣⍺⊢⍵}

Это определяет двоичную функцию, которая принимает итерации и список как левый и правый аргументы.

Спасибо @NBZ за вывод 1 байта!

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

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

  • ⍺ а также ⍵ левый и правый аргументы функции.

  • +\ кумулятивное уменьшение на сумму.

  • ⍣⍺повторяет предыдущий оператор ⍺раз.

  • ⊢⍵ применяет функцию идентификации к ⍵ .

    Это более короткий способ анализа кода (+\⍣⍺)⍵вместо +\⍣(⍺⍵).

В совокупности мы применяем +\в общей сложности ⍺раз⍵

Деннис
источник
@ Алекса: Тогда не +\⍣⎕⊢⎕будет приемлемым? ( ⎕это как Python input()).
Маринус
1
@marinus Это действительно печатает вне REPL? Единственные настольные переводчики, которые у меня есть, потребуют назначения ⎕позже.
Деннис
5

Matlab, 41 байт

function f(l,n);for i=1:n;l=cumsum(l);end

Довольно просто. Я все еще думаю, что довольно раздражает отсутствие встроенного способа создания кусочно определенных анонимных функций или якорей в рекурсиях.

Ungolfed:

function f(l,n);
for i=1:n;
    l=cumsum(l);
end
flawr
источник
5

JavaScript (ES6) 38

Удивительно маленькое рекурсивное использование .map

f=(l,n,t=0)=>n?f(l.map(x=>t+=x),n-1):l

function test()
{
  var n, v, i = I.value
  v = i.match(/\-?\d+/g).map(x=>+x)
  n = v.pop()
  console.log(v,n)
  O.innerHTML = I.value + ' -> ' + f(v,n) + '\n' + O.innerHTML;
}

test()
<input id=I value='[-3, 4, 7, -1, 15], 3'><button onclick="test()">-></button>
<pre id=O></pre>
Развернуть фрагмент

edc65
источник
5

К, 7 3 байта

{y+\/x}

Очень похоже на решение J. +\точно выполняет частичную сумму, а когда /ему предоставляется монадический глагол и целочисленный левый аргумент, он выполняет итерацию заданное число раз, как цикл for. Остальное просто аккуратно завернуть в соответствии с порядком аргументов.

  {y+\/x}[-3 4 7 -1 15;1]
-3 1 8 7 22
  {y+\/x}[-3 4 7 -1 15;3]
-3 -5 1 14 49

Проверено в Коне и Ок .

Редактировать:

Если мне разрешено изменять аргументы, как определено @ kirbyfan64sos, я могу полностью отказаться от переноса функции:

+\/

Вызывается как:

+\/[3;-3 4 7 -1 15]

Это работает правильно как в k2.8, так и в k5. Он не работает в норме, так как этот переводчик еще не поддерживает наречия карри (иначе говоря, «спроецированные»), и он не работает должным образом в Kona по менее понятным причинам.

редактировать : по состоянию на несколько дней назад, +\/формулировка также работает в ОК.

Johne
источник
1
Аргументы можно поменять местами , поэтому я думаю, что вы сможете побрить несколько байтов.
kirbyfan64sos
3 +\/ -3 4 7 -1 15прекрасно работает в Kona, но вы не можете назначить его функции. Странно ...
Деннис
Да, Кона явно не относится 3+\/-3 4 7 -1 15к тому же, что и +\/[3;-3 4 7 -1 15]заставляет меня задуматься, относятся ли они к первому как к особому синтаксическому случаю.
Джон
4

Юлия, 29 байт

f(x,y)=y>0?f(cumsum(x),y-1):x

Это действительно не нуждается в большом объяснении. Это рекурсивная функция, если y==0затем просто вывести x. В противном случае уменьшите y, выполните cumum и рекурсивно. Вероятно, не самое удачное решение Джулии, я все еще работаю над этим.

Глен О
источник
4

Лабиринт , 73 байта

;?
,"
;
#
#;}=
;  #
"#;(
_  ;={()"
#;; ( { "
  ; { !\(@
+=( =
" " "
":{:"

Прошло много времени с тех пор, как я что-то ответил в Лабиринте, и это казалось выполнимым. :)

Формат ввода представляет собой плоский список с количеством итераций, а затем (и затем со списком, к которому нужно применить частичные суммы). Разделители не имеют значения для всех, если после последнего целого числа нет символа, поэтому вы можете использовать что-то читаемое, например:

3 | -3, 4, 7, -1, 15

Вывод через новую строку:

-3
-5
1
14
49
Мартин Эндер
источник
4

R 75 байт

Это длинный, но другой вариант ... вычисление нужной последовательности напрямую вместо кумулятивных сумм:

function(x,n)sapply(1:length(x),function(i)sum(x[1:i]*choose(i:1+n-2,n-1)))

Отмечая, что коэффициенты членов xi для cumsum ^ n (x) являются диагоналями треугольника Паскаля. т.е.

cumsum^3(x) = choose(2,2) * x1, choose(3,2) * x1 + choose(2,2) *x2, choose(4,2) * x1 + choose(3,2) * x2 + choose(2,2) * x3, ....

редактировать: сделать функцию

njnnja
источник
4

Python 2, 67

Здесь используется та же сумма , что и у Энтони Ройтмана , и та же рекурсия, что и у Моргана Треппа .

f=lambda l,n:f([sum(l[:i+1])for i in range(len(l))],n-1)if n else l

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

mathmandan
источник
4

Python, 113 93 89 76 байт

def f(l,n):
 for i in[0]*n:l=[sum(l[:j+1])for j in range(len(l))];
 print(l)

Это работает для обоих тестовых случаев. Спасибо Status, Morgan Thrapp и Ruth Franklin за то, что они помогли мне сыграть в программе до 93, 89 и 76 байтов соответственно.

Энтони Ройтман
источник
1
Вы можете сократить количество байтов, изменив второй цикл в понимании списка. То есть k=[sum(l[:j+1])for j in range(len(l))]. Затем, ;k=lприкрепив конец, вы можете поместить все это в одну строку с for iциклом.
Статус
1
Вы можете переместить k=[sum(l[:j+1])for j in range(len(l))];l=kстроку на ту же строку, что и цикл for, чтобы сохранить 2 байта, и убрать пробел между аргументами f, чтобы сохранить еще один байт.
Морган Трепп
Как вы не используете значение i, вы можете заменить for i in range(n)с for i in[0]*n(потому что все , что вы заботитесь о том , длина не элементы списка). И я думаю, что вы можете сделать это, не используя вспомогательный список k, просто изменив аргумент l.
Рут Франклин
4

Gol> <> 0.3.10 , 22 байта

SI
C>rFlMF:}+
NRl<C}<;

Первое целое число принимается за номер итерации, а остальные составляют список. Окончательный список выводится с новой строкой.

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

объяснение

SI            Read integer, moving down on EOF (first line runs as loop)
r             Reverse stack, putting iteration number on top

[outer loop]
F             Do #(iterations) times

[inner loop]
lMF           Do #(length of stack - 1) times
:             Duplicate top of stack
}             Rotate stack rightward (top goes to bottom)
+             Add the top two elements of the stack
C             Continue inner loop, moving down from F when loop is over

}             Rotate once more
C             Continue outer loop, moving down from F when loop is over

lRN           Print stack as (num + newline)
;             Halt

Чтобы понять, почему это работает, давайте попробуем небольшой пример [5 2 1]:

[5 2 1] -- : --> [5 2 1 1] -- } -->  [1 5 2 1]  -- + --> [1 5 3]
[1 5 3] -- : --> [1 5 3 3] -- } -->  [3 1 5 3]  -- + --> [3 1 8]

-- } --> [8 3 1]
Sp3000
источник
3

Python, 52 байта

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Рекурсивная функция, которая повторяется как по списку, так lи по количеству итераций n. Давайте разберемся с этим.

Во-первых, давайте рассмотрим рекурсивную функцию, gкоторая повторяла частичную сумму только один раз.

g=lambda l:l and g(l[:-1])+[sum(l)]

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

Теперь давайте посмотрим на функцию, fкоторая применяется gдля nитераций.

f=lambda l,n:n and f(g(l),n-1)or l

Когда nесть 0, это возвращает список lбез изменений, и в противном случае, применяется gодин раз, затем вызываетf рекурсивно с оставшимся меньшим количеством итераций.

Теперь давайте снова посмотрим на реальный код, который объединяет две рекурсии в одну функцию. Идея состоит в том, чтобы рассматривать g(l)как особый случай f(l,1).

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Мы взяли f(g(l),n-1)из предыдущего определения, расширяется g(l)в g(l[:-1])+[sum(l)], а затем заменить g(_)с f(_,1)на приурочены рекурсивные вызовы вf .

Для базового случая мы хотим вернуться lвсякий раз, когда n==0или l==[]. Мы объединяем их, отмечая, что любой из них n*lявляется пустым списком, то есть ложью. Итак, мы возвращаемся, когда n*lне пусто, и возвращаемl противном случае.

Даже если есть два рекурсивных вызова f, это не вызывает экспоненциального увеличения рекурсивного определения чисел Фибоначчи, но остается квадратичным.

XNOR
источник
3

C ++ (61 + 17 = 78 байт)

#include<numeric>
void f(int*a,int*e,int n){for(;n--;)std::partial_sum(a,e,a);}

Прецедент:

#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    f(a, std::end(a), 3);
    for (auto i : a)
        std::cout << i << " ";
}

Это требует некоторой свободы со спецификацией: он использует массив в стиле C, передавая указатели на начало и конец массива. Внутренне, как вы можете видеть, это только очень тонкая оболочка вокругstd::partial_sum в стандартной библиотеке. Вместо того, чтобы фактически возвращать полученное значение, он просто изменяет массив, который передается.

Если мы не возражаем выдвинуть определения вещей до предела (и, возможно, немного выше), мы можем определить «функцию» в лямбда-выражении:

#include<numeric>
#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    int *e = std::end(a);
    int n=3;

    auto f=[&]{for(;n--;)std::partial_sum(a,e,a);};

    f();
    for (auto i : a)
        std::cout << i << " ";
}

Это уменьшает определение функции (-подобного объекта) до этой части:

[&]{for(;n--;)std::partial_sum(a,e,a);};

... для 40 байтов (+17 для #include).

Джерри Гроб
источник
Вау, я не ожидал, что у STL будет alg для подсчета частичных сумм.
Зерегес
1
@Zereges: Никто не ожидает испанского Inquisit .... о, подождите, мы делаем C ++, а не Python. Мои извенения.
Джерри Коффин
2

Haskell, 52 47 байт

Первый в истории кодекс «попытка», и я очень начинающий на Haskell, поэтому комментарии с радостью приветствуются! В вопросе не было ясно, какой формат необходим для вызова функции или был ли он принят в качестве аргумента для программы, поэтому я использовал восклицательный знак в качестве идентификатора функции, чтобы сохранить пару пробелов.

0!a=a
i!a=(i-1)![sum$take j a|j<-[1..length a]]

Использование (GHCi):

$ ghci partialsums.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( partialsums.hs, interpreted )
Ok, modules loaded: Main.
*Main> 1![-3, 4 ,7 ,-1 ,15]
[-3,1,8,7,22]
*Main> 3![-3, 4 ,7 ,-1 ,15]
[-3,-5,1,14,49]
Джейк
источник
Добро пожаловать в код гольф! Как правило, сопоставление с образцом короче, чем использование охраны 0!a=a i!a=....
xnor
Спасибо @xnor - я ранее использовал 'xs' при создании исходного кода и, должно быть, пропустил его, когда модифицировал код в посте. Ред.
Джейк,
Ибо sum(take j a)вы можете избегать прощения sum$take j a, используя высокий приоритет $.
xnor
Спасибо за помощь! По какой-то причине у меня сложилось впечатление, что он $будет иметь приоритет над синтаксисом (и попытаться оценить оставшуюся часть строки в ее нынешнем виде). Конечно, это даже не имеет смысла.
Джейк,
2

R, 41 байт

function(x,n){for(i in 1:n)x=cumsum(x);x}
flodel
источник
2

C #, 52 + 85 = 148 137 байт

using E=System.Collections.Generic.IEnumerable<int>;

а также

E I(E s,int i){int t=0;return i<1?s:I(System.Linq.Enumerable.Select(s,v=>t+=v),i-1);}

Он использует неортодоксальные практики ( v=>t+=v), но это PPCG. Также обратите внимание на ограничение глубины стека.

LegionMammal978
источник
2

Python 3, 73

Вероятно, может быть в гольф немного дальше.

def f(n,i):
 p=0;c=[]
 for m in n:p+=m;c+=[p]
 f(c,i-1)if i else print(n)

Эта версия использует NumPy, что немного похоже на читерство, но вот оно:

Python 3 (с numpy), 72

from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)
Морган Трепп
источник
2

C ++ 14, 102 103 94 + 17 (включая) = 111 байт

#include<vector>
auto f(std::vector<int>a,int n){for(;n--;)for(int i=0;i<a.size()-1;++i)a[i+1]+=a[i];return a;}

Ungolfed, с тестовым набором

#include <vector>
#include <iostream>

auto f(std::vector<int> a, int n)
{
    for (; n--;)
        for (int i = 0; i < a.size() - 1; ++i)
            a[i + 1] += a[i];
    return a;
}


int main()
{
    auto t = f({-3, 4, 7, -1, 15}, 3);
    for (int i : t)
        std::cout << i << " ";
}

Полагается на порядок оценки. Не уверен, что это UB или нет, но работает. Это зависит от компилятора, поэтому я изменил его.

Zereges
источник
Вместо того, чтобы считать jот 0 до n, отсчитайте nдо 0. По моим подсчетам выдает 97 байт.
Джерри Коффин
@JerryCoffin Спасибо ..
Зерегес
1

Октава, 24 байта

@(l,n)l*triu(0*l'*l+1)^n
alephalpha
источник
1

Бурлеск, 10 байт

{q++pa}jE!

это не очень эффективно в целом, но это помогает.

blsq ) {-3 4 7 -1 15} 1 {q++pa}jE!
{-3 1 8 7 22}
blsq ) {-3 4 7 -1 15} 3 {q++pa}jE!
{-3 -5 1 14 49}
mroman
источник
1

C ++ 14, 67 байт

Как безымянная лямбда, изменяющая свой вход, требующая cв качестве контейнера произвольного доступа, подобного vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}
Карл Напф
источник
1

05AB1E , 4 байта (возможно, не конкурирующие)

F.pO

F    # Implicitly take first input and loop n times.
 .p  # Generate prefixes of input.
   O # Sum all prefixes (implicitly vectorized).

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

Урна волшебного осьминога
источник
1

Желе , 3 байта

SƤ¡

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

Это мой ( мистер Xcoder ) метод.

Желе , 3 байта

+\¡

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

Это Кейрд .

Способ № 1

SƤ¡ - Полная программа, диадический.

  ¡- применить несколько раз, N раз.
 Ƥ - сопоставить предыдущую ссылку с префиксами списка.
S - сумма
     - вывод неявно

Способ № 2

+ \ ¡- Полная программа, двоичная.

  ¡- применить несколько раз, N раз.
 \ - совокупное уменьшение на:
+ - Дополнение.
Mr. Xcoder
источник
0

Аксиома 213 47 байт

m(a,b)==(for i in 1..b repeat a:=scan(+,a,0);a)

ungolf и некоторые примеры

 (3) -> [m([-3,4,7,-1,15],1), m([-3,4,7,-1,15],3)]
    Compiling function l with type List Integer -> List Integer
    Compiling function m with type (List Integer,Integer) -> List
       Integer

    (3)  [[- 3,1,8,7,22],[- 3,- 5,1,14,49]]
                                                       Type: List List Integer
RosLuP
источник