Somas parciais iteradas

23

As somas parciais de uma lista de números inteiros [a 1 , a 2 , a 3 , ..., a n ] são

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

Podemos então pegar a lista de somas parciais [s 1 , s 2 , s 3 , ..., s n ] e computar suas somas parciais novamente para produzir uma nova lista, e assim por diante.

Relacionado: Diferenças avançadas iteradas

Entrada:

  • Uma lista não vazia de números inteiros
  • Um número positivo de iterações,

Saída: imprima ou retorne a lista de números inteiros resultante da soma parcial várias vezes.

Menos bytes ganha. Os embutidos são bons, mesmo que resolvam completamente o problema.

Casos de teste:

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

Entre os melhores:

Mostrar snippet de código

code-golf number arithmetic sequence array-manipulation xnor
fonte
Os argumentos precisam estar na mesma ordem ou o número de iterações pode vir antes da lista de números?
kirbyfan64sos
@ kirbyfan64sos Qualquer pedido.
Xnor

Respostas:

14

J, 5 bytes

+/\^:

Experimente online em J.js .

Como funciona

  • /\ é um advérbio (função que recebe um argumento à esquerda) que reduz cumulativamente por seu argumento.

  • Assim +/\é o verbo da soma cumulativa .

  • ^:é a conjunção de poder ; (f ^: n) yaplica fum total den vezes a y.

  • O trem verbo-conjunção +/\^:forma um advérbio que repete+/\ quantas vezes for especificado em seu argumento (esquerdo).

    x (+/\^:) yé analisado como (x (+/\^:)) y, o que é equivalente à execução (+/\^:x) y.

Obrigado a @ Zgarb por sua ajuda com a explicação.

Dennis
fonte
13

Mathematica, 19 bytes

Bem, se os embutidos estiverem bem ...

Accumulate~Nest~##&

Define uma função com a mesma assinatura que os exemplos no desafio. Tenho certeza, graças ao nome longoAccumulate que isso será facilmente derrotado pelas línguas do golfe e pela família APL. :)

Para elaborar o comentário de LegionMammal978 para aqueles que não fazem o Mathematica:

##representa uma sequência dos parâmetros da função (que é como uma lista que "se espalha automaticamente" onde quer que seja inserida, se você estiver mais familiarizado com esse termo do idioma de sua escolha). O ~são açúcar sintático para chamada de função infix, por isso, se nós chamamos a função com parâmetros liste ne expandir tudo, temos:

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

Que passa a ser exatamente a ordem dos argumentos esperada por Nest.

Martin Ender
fonte
Isso é interessante, usando a notação infix para 3 argumentos, usando SlotSequence... #
7891
9

Haskell, 26 23 bytes

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

Isso define uma função anônima, chamada da seguinte maneira:

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

Obrigado a @nimi por salvar 3 bytes.

Explicação

(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument
Zgarb
fonte
Muito agradável! E obrigado pela explicação!
Jake #
2
Go pointfree, então você pode até omitir o nome para a função: (!!).iterate(scanl1(+)).
N /
@nimi Obrigado! De alguma forma, eu raciocinei que a composição não funcionaria para minha vantagem aqui ...
Zgarb
9

APL, 9 8 bytes

{+\⍣⍺⊢⍵}

Isso define uma função diádica que aceita as iterações e lista como argumentos esquerdo e direito.

Obrigado a @NBZ por jogar fora um byte!

Experimente online no TryAPL .

Como funciona

  • ⍺e ⍵são os argumentos esquerdo e direito da função.

  • +\ é cumulativo reduzir pela soma.

  • ⍣⍺repete os ⍺tempos anteriores do operador .

  • ⊢⍵aplica a função de identidade a ⍵.

    Esta é uma maneira mais curta de analisar o código como em (+\⍣⍺)⍵vez de +\⍣(⍺⍵).

Em conjunto, aplicamos +\um total de ⍺vezes a⍵

Dennis
fonte
@AlexA .: Então não +\⍣⎕⊢⎕seria aceitável? ( ⎕é como Python input()).
marinus
1
@ marinus Isso realmente imprime fora de um REPL? Os únicos intérpretes de área de trabalho que eu tenho exigiriam a atribuição ⎕posteriormente.
Dennis
5

Matlab, 41 bytes

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

Bem direto. Eu ainda acho bastante irritante não ter construído uma maneira de criar funções anônimas definidas por partes ou âncoras em recursões.

Ungolfed:

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

JavaScript (ES6) 38

Surpreendentemente pequeno usando .map recursivamente

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>
Expandir snippet

edc65
fonte
5

K, 7 3 bytes

{y+\/x}

Muito parecido com a solução J. +\executa com precisão uma soma parcial e, quando /é fornecido com um verbo monádico e um argumento inteiro à esquerda, itera um número especificado de vezes, como um loop "for". O resto é apenas resumir tudo de acordo com a ordem dos argumentos.

  {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

Testado em Kona e OK .

Editar:

Se eu puder reverter os argumentos, como @ kirbyfan64sos determinou, eu posso dispensar completamente a função wrapping:

+\/

Chamado como:

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

Isso funciona corretamente nos k2.8 e k5. Ele não funciona bem, pois esse intérprete ainda não suporta advérbios ao curry (também conhecidos como "projetados") e não parece funcionar corretamente no Kona por razões menos claras.

editar : Há alguns dias, a +\/formulação também funciona em OK.

JohnE
fonte
1
Os argumentos podem ser revertidos , então acho que você poderá raspar alguns bytes.
kirbyfan64sos
3 +\/ -3 4 7 -1 15funciona bem no Kona, mas você não pode atribuí-lo a uma função. Estranho ...
Dennis
Sim, Kona claramente não está tratando 3+\/-3 4 7 -1 15o mesmo que +\/[3;-3 4 7 -1 15]- me faz pensar se eles lidam com o primeiro como um caso sintático especial.
Johne
4

Pitão, 9 bytes

usM._GvwQ

Experimente on-line: Demonstration or Test Suite

Explicação

usM._GvwQ  implicit: Q = input list
      vw   input number
u       Q  repeat the following instruction ^ times to G = Q
   ._G        sequence of prefixes of G
 sM           sum them up
Jakube
fonte
4

Julia, 29 bytes

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

Isso realmente não precisa de muita explicação. É uma função recursiva; se for y==0, basta gerar x. Caso contrário, diminua y, execute um cumsum e execute novamente. Provavelmente não é a solução Julia mais golfe possível, ainda estou trabalhando nisso.

Glen O
fonte
4

Labirinto , 73 bytes

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

Já faz um tempo desde que eu respondi alguma coisa no Labyrinth, e isso parecia factível. :)

O formato de entrada é uma lista simples com o número de iterações primeiro (e depois a lista à qual aplicar as somas parciais). Os delimitadores não importam tudo, desde que não exista um caractere após o último número inteiro; portanto, você pode usar algo legível como:

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

A saída é separada por nova linha:

-3
-5
1
14
49
Martin Ender
fonte
4

R, 75 bytes

É longo, mas uma abordagem diferente ... computando a sequência desejada diretamente em vez de somas cumulativas:

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

Observando que os coeficientes dos termos de xi para cumsum ^ n (x) são diagonais do triângulo de Pascal. ie

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, ....

edit: para criar uma função

njnnja
fonte
4

Python 2, 67

Isso usa o mesmo somatório de Anthony Roitman e a mesma recursão de Morgan Thrapp .

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

Eu desenvolvi essa solução antes de ver a deles, e então parecia mais fácil publicá-la como uma resposta do que como um comentário para um ou ambos.

mathmandan
fonte
4

Python, 113 93 89 76 bytes

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

Funciona para os dois casos de teste. Agradeço a Status, Morgan Thrapp e Ruth Franklin por me ajudarem a reduzir o programa para 93, 89 e 76 bytes, respectivamente.

Anthony Roitman
fonte
1
Você pode cortar um número de bytes alterando o segundo loop para uma compreensão da lista. Isto é k=[sum(l[:j+1])for j in range(len(l))]. Em seguida, com o ;k=ltacheado no final, você pode colocar tudo isso em uma linha com o for iloop.
Status
1
Você pode mover k=[sum(l[:j+1])for j in range(len(l))];l=kpara a mesma linha do loop for para economizar 2 bytes e remover o espaço entre os argumentos de f para salvar outro byte.
Morgan Thrapp
Como você não usa o valor de i, você pode substituir for i in range(n)por for i in[0]*n(porque tudo o que importa é o comprimento e não os elementos da lista). E acho que você pode fazer isso sem usar a lista auxiliar k, apenas modificando o argumento l.
Ruth Franklin
4

Gol> <> 0.3.10 , 22 bytes

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

O primeiro número inteiro é considerado o número da iteração e o restante compõe a lista. A lista final é emitida separada por nova linha.

A linguagem ainda é bastante jovem e instável, mas, como estou bastante focada nesses operadores, pensei que tudo ficaria bem.

Explicação

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

Para ver por que isso funciona, vamos tentar um pequeno exemplo [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
fonte
3

Python, 52 bytes

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

Uma função recursiva que recorrente tanto na lista l e no número de iterações n. Vamos dividir.

Primeiro, vamos considerar uma função recursiva g que iterou a soma parcial apenas uma vez.

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

Para uma lista vazia l, ela retorna la lista vazia. Caso contrário, a última entrada dos montantes parciais del é a soma geral de l, que é anexada ao resultado recursivo para todos, exceto o último elemento de l.

Agora, vejamos uma função fque se aplica ga niterações.

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

Quando né 0, isso retorna a lista linalterada e, caso contrário, aplica-se guma vez e chamaf recursivamente com menos uma iteração restante.

Agora, vejamos novamente o código real, que combina as duas recursões em uma única função. A idéia é tratar g(l)como o caso especial f(l,1).

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

Pegamos f(g(l),n-1)a partir da definição anterior, expandida g(l)em g(l[:-1])+[sum(l)], em seguida, substituídog(_) por f(_,1)para limitar as chamadas recursivas para f.

Para o caso base, queremos retornar lsempre que n==0ou l==[]. Combinamos isso observando que qualquer um deles fazn*l da lista vazia, que é Falsy. Portanto, recursamos sempre que n*lnão estiver vazio e retornamos o lcontrário.

Embora existam duas chamadas recursivas para f, isso não causa uma explosão exponencial na definição recursiva dos números de Fibonacci, mas permanece quadrático.

xnor
fonte
3

C ++ (61 + 17 = 78 bytes)

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

Caso de teste:

#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 << " ";
}

Isso requer uma certa liberdade com a especificação: ele usa uma matriz no estilo C, passando ponteiros para o início e o final da matriz. Internamente, como você pode ver, é apenas um invólucro extremamente fino std::partial_sumna biblioteca padrão. Em vez de realmente retornar o valor resultante, apenas modifica a matriz que é passada.

Se não nos importamos em levar definições de coisas ao limite (e, sem dúvida, um pouco além), podemos definir uma "função" em uma expressão lambda:

#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 << " ";
}

Isso reduz a definição da função (objeto semelhante) a esta peça:

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

... para 40 bytes (+17 para o #include).

Jerry Coffin
fonte
Wau, eu não esperava que a STL tivesse alg para contar somas parciais.
Zereges
1
@Zereges: ninguém espera o Inquisit espanhol .... oh, espere, estamos fazendo C ++, não Python. Me desculpe.
Jerry Coffin
2

Haskell, 52 47 bytes

Primeira tentativa de código de golfe, e eu sou muito iniciante em Haskell, então os comentários são bem-vindos! Não ficou claro na pergunta sobre qualquer formato necessário da chamada de função ou se foi levado por um argumento para o programa, então usei o ponto de exclamação como identificador da função para economizar alguns espaços.

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

Uso (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]
Jake
fonte
Bem-vindo ao código de golfe! Geralmente é mais curto para combinar padrões do que usar guardas, como 0!a=a i!a=....
Xnor
Obrigado @xnor - Eu já havia usado 'xs' ao criar o código inicial e deve ter perdido quando modifiquei o código no post. Editado.
Jake
Pois sum(take j a), você pode evitar parênteses sum$take j a, usando a alta precedência de $.
Xnor
Obrigado pela ajuda! Por algum motivo, fiquei com a impressão de que $teria precedência sobre a sintaxe (e tentaria avaliar o restante da linha como está). Claro, isso nem faria sentido.
Jake #
2

R, 41 bytes

function(x,n){for(i in 1:n)x=cumsum(x);x}
flodel
fonte
2

C #, 52 + 85 = 148 137 bytes

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

e

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

Ele usa práticas não-ortodoxas ( v=>t+=v), mas esse é o PPCG. Observe também a restrição de profundidade da pilha.

LegionMammal978
fonte
2

Python 3, 73

Provavelmente poderia ser jogado um pouco mais longe.

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

Esta versão usa numpy, que parece um pouco de trapaça, mas aqui está:

Python 3 (com numpy), 72

from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)
Morgan Thrapp
fonte
2

C ++ 14, 102 103 94 + 17 (incluir) = 111 bytes

#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, com caso de teste

#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 << " ";
}

Depende da ordem da avaliação. Não tenho certeza se é UB ou não, mas funciona Depende do compilador, então eu mudei.

Zereges
fonte
Em vez de contar jde 0 a n, conte naté 0. Dá 97 bytes pela minha contagem.
Jerry Coffin
@JerryCoffin Thanks ..
Zereges
1

Oitava, 24 bytes

@(l,n)l*triu(0*l'*l+1)^n
alefalpha
fonte
1

Burlesco, 10 bytes

{q++pa}jE!

não é muito eficiente em geral, mas funciona.

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
fonte
1

C ++ 14, 67 bytes

Como lambda sem nome, modificando sua entrada, exigindo ccomo um contêiner de acesso aleatório vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}
Karl Napf
fonte
1

05AB1E , 4 bytes (provavelmente não concorrente)

F.pO

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

Experimente online!

Urna de polvo mágico
fonte
0

Axiom 213 47 bytes

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

ungolf e algum exemplo

 (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
fonte